宠物小精灵之收服

宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。

一天，小智和皮卡丘来到了小精灵狩猎场，里面有很多珍贵的野生宠物小精灵。

小智也想收服其中的一些小精灵。

然而，野生的小精灵并不那么容易被收服。

对于每一个野生小精灵而言，小智可能需要使用很多个精灵球才能收服它，而在收服过程中，野生小精灵也会对皮卡丘造成一定的伤害（从而减少皮卡丘的体力）。

当皮卡丘的体力小于等于 $0$ 时，小智就必须结束狩猎（因为他需要给皮卡丘疗伤），而使得皮卡丘体力小于等于 $0$ 的野生小精灵也不会被小智收服。

当小智的精灵球用完时，狩猎也宣告结束。

我们假设小智遇到野生小精灵时有两个选择：收服它，或者离开它。

如果小智选择了收服，那么一定会扔出能够收服该小精灵的精灵球，而皮卡丘也一定会受到相应的伤害；如果选择离开它，那么小智不会损失精灵球，皮卡丘也不会损失体力。

小智的目标有两个：主要目标是收服尽可能多的野生小精灵；如果可以收服的小精灵数量一样，小智希望皮卡丘受到的伤害越小（剩余体力越大），因为他们还要继续冒险。

现在已知小智的精灵球数量和皮卡丘的初始体力，已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。

请问，小智该如何选择收服哪些小精灵以达到他的目标呢？

输入格式

输入数据的第一行包含三个整数：$N$，$M$，$K$，分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。

之后的 $K$ 行，每一行代表一个野生小精灵，包括两个整数：收服该小精灵需要的精灵球的数量，以及收服过程中对皮卡丘造成的伤害。

输出格式

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

数据范围

$0 < N /leq 1000$,
$0 < M /leq 500$,
$0 < K /leq 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

 

解题思路

　　这题本质是二维费用的背包问题，可以用多种方式来定义状态。

 

解法一

　　$f /left( {i,j,k} /right)$表示所有从前$i$个精灵中选，且精灵球消耗不超过$j$，体力不超过$k$的方案的价值的最大值。这里的价值指捕捉到的精灵的个数。根据第$i$个精灵选或不选来进行集合的划分，因此状态转移方程为$$f /left( {i,j,k} /right) = max /left/{ f /left( {i-1,j,k} /right),~ f /left( {i-1,j-v_{1i},k-v_{2i}} /right) + 1 /right/}$$

　　其中$v_{1i}$表示捕捉第$i$个精灵所需要消耗的精灵球数量，$v_{2i}$表示捕捉第$i$个精灵所需要消耗的体力值。

　　时间复杂度为$O /left( N /times M /times K /right)$。

　　AC代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 1010;
 5 
 6 int f[N][N];
 7 
 8 int main() {
 9     int n, m1, m2;
10     scanf("%d %d %d", &m1, &m2, &n);
11     for (int i = 1; i <= n; i++) {
12         int v1, v2;
13         scanf("%d %d", &v1, &v2);
14         for (int j = m1; j >= v1; j--) {
15             for (int k = m2; k > v2; k--) {
16                 f[j][k] = max(f[j][k], f[j - v1][k - v2] + 1);
17             }
18         }
19     }
20     
21     for (int i = 0; i < m2; i++) {
22         if (f[m1][i + 1] == f[m1][m2]) {
23             printf("%d %d", f[m1][m2], m2 - i);
24             break;
25         }
26     }
27     
28     return 0;
29 }

 

解法二

　　$f /left( {i,j,k} /right)$表示所有从前$i$个精灵中选，且精灵球消耗不超过$j$，恰好捕捉了$k$个精灵的方案所消耗体力的最小值。一样根据第$i$个精灵选或不选来进行集合的划分，因此状态转移方程为$$f /left( {i,j,k} /right) = min /left/{ f /left( {i-1,j,k} /right),~ f /left( {i-1,j-v_{1i},k-1 } /right) + v_{2i} /right/}$$

　　时间复杂度为$O /left( N^2 /times K /right)$。

　　AC代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 1010;
 5 
 6 int f[N][N];
 7 
 8 int main() {
 9     int n, m, k;
10     scanf("%d %d %d", &m, &k, &n);
11     
12     memset(f, 0x3f, sizeof(f));
13     for (int i = 0; i <= m; i++) {
14         f[i][0] = 0;
15     }
16     for (int i = 1; i <= n; i++) {
17         int v1, v2;
18         scanf("%d %d", &v1, &v2);
19         for (int j = m; j >= v1; j--) {
20             for (int u = i; u; u--) {
21                 f[j][u] = min(f[j][u], f[j - v1][u - 1] + v2);
22             }
23         }
24     }
25     
26     for (int i = n; i >= 0; i--) {
27         if (f[m][i] < k) {
28             printf("%d %d", i, k - f[m][i]);
29             break;
30         }
31     }
32     
33     return 0;
34 }

 

解法三

　　$f /left( {i,j,k} /right)$表示所有从前$i$个精灵中选，且体力消耗不超过$j$，恰好捕捉了$k$个精灵的方案所消耗精灵球的最小值。一样根据第$i$个精灵选或不选来进行集合的划分，因此状态转移方程为$$f /left( {i,j,k} /right) = min /left/{ f /left( {i-1,j,k} /right),~ f /left( {i-1,j-v_{2i},k-1 } /right) + v_{1i} /right/}$$

　　时间复杂度为$O /left( N^2 /times M /right)$。

　　AC代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 510;
 5 
 6 int f[N][N];
 7 
 8 int main() {
 9     int n, m, k;
10     scanf("%d %d %d", &k, &m, &n);
11     
12     memset(f, 0x3f, sizeof(f));
13     for (int i = 0; i <= m; i++) {
14         f[i][0] = 0;
15     }
16     for (int i = 1; i <= n; i++) {
17         int v1, v2;
18         scanf("%d %d", &v1, &v2);
19         for (int j = m; j > v2; j--) {
20             for (int u = i; u; u--) {
21                 f[j][u] = min(f[j][u], f[j - v2][u - 1] + v1);
22             }
23         }
24     }
25     
26     for (int i = n; i >= 0; i--) {
27         for (int j = 0; j < m; j++) {
28             if (f[j + 1][i] <= k) {
29                 printf("%d %d", i, m - j);
30                 return 0;
31             }
32         }
33     }
34     
35     return 0;
36 }

 

参考资料

　　AcWing 1022. 宠物小精灵之收服：https://www.acwing.com/video/368/