1022 宠物小精灵之收服（二维费用的零一背包问题）

迈不过友情╰ 2022-09-10 14:17 184阅读 0赞

**1. 问题描述：**

宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。一天，小智和皮卡丘来到了小精灵狩猎场，里面有很多珍贵的野生宠物小精灵。小智也想收服其中的一些小精灵。然而，野生的小精灵并不那么容易被收服。对于每一个野生小精灵而言，小智可能需要使用很多个精灵球才能收服它，而在收服过程中，野生小精灵也会对皮卡丘造成一定的伤害（从而减少皮卡丘的体力）。当皮卡丘的体力小于等于0时，小智就必须结束狩猎（因为他需要给皮卡丘疗伤），而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。  
当小智的精灵球用完时，狩猎也宣告结束。我们假设小智遇到野生小精灵时有两个选择：收服它，或者离开它。如果小智选择了收服，那么一定会扔出能够收服该小精灵的精灵球，而皮卡丘也一定会受到相应的伤害；如果选择离开它，那么小智不会损失精灵球，皮卡丘也不会损失体力。  
小智的目标有两个：主要目标是收服尽可能多的野生小精灵；如果可以收服的小精灵数量一样，小智希望皮卡丘受到的伤害越小（剩余体力越大），因为他们还要继续冒险。  
现在已知小智的精灵球数量和皮卡丘的初始体力，已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。请问，小智该如何选择收服哪些小精灵以达到他的目标呢？

**输入格式**

输入数据的第一行包含三个整数：N，M，K，分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。之后的K行，每一行代表一个野生小精灵，包括两个整数：收服该小精灵需要的精灵球的数量，以及收服过程中对皮卡丘造成的伤害。

**输出格式**

输出为一行，包含两个整数：C，R，分别表示最多收服C个小精灵，以及收服C个小精灵时皮卡丘的剩余体力值最多为R。

**数据范围**

0 < N ≤ 1000，  
0 < M ≤ 500，  
0 < K ≤ 100

**输入样例1：**

10 100 5  
7 10  
2 40  
2 50  
1 20  
4 20

**输出样例1：**

3 30

**输入样例2：**

10 100 5  
8 110  
12 10  
20 10  
5 200  
1 110

**输出样例2：**

0 100

来源：[https://www.acwing.com/problem/content/description/1024/][https_www.acwing.com_problem_content_description_1024]

**2. 思路分析：**

这道题目属于阅读理解的题目，首先我们需要根据故事背景将其抽象成一种具体的模型，由题目可知属于选择性的问题，我们需要选择一些小精灵并且收服他们，所以对于每一只小精灵来说可以选也可以不选，而且选择小精灵的时候是没有顺序的，根据这两个特点可以知道属于经典的零一背包问题，由题目可知，这道题目存在两个花费，分别是消耗的精灵球的数量和皮卡丘的体力值，所以属于**二维费用的零一背包**问题，类似于一维的零一背包问题，我们可以定义一个二维数组或者列表dp，其中dp\[j\]\[k\]表示消耗的精灵球数量为j，消耗的皮卡丘的体力值为k之后能够收服最多的小精灵的数量，我们使用三层循环遍历即可，第一层循环枚举每一只小精灵，第二层循环逆序枚举消耗的小精灵的数量，第三层逆序循环枚举消耗的皮卡丘的体力值，逆序枚举其实类似于一维的零一背包问题，并且需要注意的一个问题是皮卡丘的体力值必须大于0才能够收服小精灵所以我们在遍历消耗皮卡丘的体力值的时候从皮卡丘初始最大的体力值减1开始遍历，这样可以保证皮卡丘的体力值是大于0的时候收服小精灵的，并且题目中还需要求解出皮卡丘剩余的最多体力值，其实我们逆序遍历找到第一个k使得dp\[V1\]\[k\]等于dp\[V1\]\[V2 - 1\]即可。

**3. 代码如下：**

if __name__ == '__main__':
        # V1表示总的精灵球的数量, V2表示皮卡丘的体力值, n表示小精灵的数量
        V1, V2, n = map(int, input().split())
        dp = [[0] * (V2 + 1) for i in range(V1 + 1)]
        for i in range(n):
            # v1表示当前小精灵需要消耗的精灵球的数量, v2表示需要消耗皮卡丘的体力值
            v1, v2 = map(int, input().split())
            for j in range(V1, v1 - 1, -1):
                # 因为皮卡丘的体力值需要大于等于0所以遍历的时候需要V2 - 1开始遍历
                for k in range(V2 - 1, v2 - 1, -1):
                    dp[j][k] = max(dp[j][k], dp[j - v1][k - v2] + 1)
        print(dp[V1][V2 - 1], end=" ")
        k = V2 - 1
        while k > 0 and dp[V1][k - 1] == dp[V1][V2 - 1]: k -= 1
        print(V2 - k)

[https_www.acwing.com_problem_content_description_1024]: https://www.acwing.com/problem/content/description/1024/