题解——二维费用背包问题（宠物小精灵之收服、潜水员）
宠物小精灵之收服：
小智想收服一些小精灵。
对于每一个野生小精灵而言，小智可能需要使用很多个精灵球才能收服它，而在收服过程中，野生小精灵也会对皮卡丘造成一定的伤害。
当皮卡丘的体力小于等于0或者精灵球用完时，小智就必须结束狩猎。
小智的目标有两个：主要目标是收服尽可能多的野生小精灵；如果可以收服的小精灵数量一样，小智希望皮卡丘受到的伤害越小。
输入格式：
输入数据的第一行包含三个整数：N，M，K，分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。
输出格式：
输出为一行，包含两个整数：C，R，分别表示最多收服C个小精灵，以及收服C个小精灵时皮卡丘的剩余体力值最多为R。
二维的01背包问题，像普通01背包一样做就行，只是加一层循环。最后输出f[n][m]（n个球，m个体力）。要输出剩下的体力值，我们遍历f[n][0]~f[n][m]即可。
题目要求当体力为0的时候算抓捕失败，所以我们把m-1当做m带入计算即可。
代码如下：
#include
using namespace std;
const int N=1010;
int f[N][N];
int n,m,k;//拥有的球数和体力值、精灵数
int main(){cin>>n>>m>>k;int a,b;//每只精灵需要的球数和照成的伤害for(int i=0;i>a>>b;for(int j=n;j>=a;j--)//遍历球数for(int u=m-1;u>=b;u--)//遍历体力f[j][u]=max(f[j][u],f[j-a][u-b]+1);}int tmp=0;for(int i=m;i>=0;i--)if(f[n][i]==f[n][m-1])tmp=i;cout< 潜水员：
潜水员为了潜水要使用特殊的装备。
他有一个带2种气体的气缸：一个为氧气，一个为氮气。
每个气缸都有重量和气体容量。
他完成工作所需气缸的总重的最低限度的是多少？
输入格式：
第一行有2个整数 m，n。它们表示氧，氮各自需要的量。
第二行为整数 k 表示气缸的个数。
此后的 k 行，每行包括ai，bi，ci，3个整数。这些各自是：第 i 个气缸里的氧和氮的容量及气缸重量。
输出格式：
仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。
二维费用的01背包问题。f[i][j][k]代表只看前i个气缸，氧气至少为j，氮气至少为k时的最大重量（注意氧气和氮气可以多）。
选第i个：
f[i][j][k] = f[i - 1][j - o2[i]][k - n2[i]]不选第i个：
f[i][j][k] = f[i - 1][j][k]。本题要求的是最小值，为了不被初始值0影响，需要把所有状态更新为INF，特别的f[i][0][0]=0。
并且在两重循环中，需要更新到0而不是v，因为是最少需要多少氧气和氮气，所以小于v的部分也是有效的，要把小于v的部分更新出来，而不是让他保留INF的值。
代码如下：
#include
#include
using namespace std;const int N = 1010;
int f[N][N];//o2,n2
int n, m;//o2,n2int main() {cin >> n >> m;int s, o2, n2, m2;cin >> s;memset(f, 0x3f, sizeof f);f[0][0] = 0;for (int i = 0; i < s; i++) {cin >> o2 >> n2 >> m2;for (int j = n; j >= 0; j--)for (int k = m; k >= 0; k--)f[j][k] = min(f[j][k], f[max(j - o2, 0)][max(k - n2, 0)] + m2);}cout << f[n][m];return 0;
}
下一篇：如何对测试进行划分（一）