题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=2159
思路：求剩余的最大忍耐度，二维完全背包。
二维费用背包问题：
问题
二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为w[i]。
算法
费用加了一维，只需状态也加一维即可。设f[i][v][u]表示前i件物品付出两种代价分别为v和u时可获得的最大价值。状态转移方程就是：
f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}
如前述方法，可以只使用二维的数组：当每件物品只可以取一次时变量v和u采用逆序的循环，当物品有如完全背包问题时采用顺序的循环。当物品有如多重背包问题时拆分物品。这里就不再给出伪代码了，相信有了前面的基础，你能够自己实现出这个问题的程序。
物品总个数的限制（？？？）
有时，“二维费用”的条件是以这样一种隐含的方式给出的：最多只能取M件物品。这事实上相当于每件物品多了一种“件数”的费用，每个物品的件数费用均为1，可以付出的最大件数费用为M。换句话说，设f[v][m]表示付出费用v、最多选m件时可得到的最大价值，则根据物品的类型（01、完全、多重）用不同的方法循环更新，最后在f[0..V][0..M]范围内寻找答案。
AC代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<climits> using namespace std; #define INF 1000005 //a是得到的经验值，b是减掉的忍耐度 //n是还需要的经验值，m是还剩下的忍耐度 int dp[105][105]; int a[105],b[105]; int main() { int n,m,k,s; while(scanf("%d%d%d%d",&n,&m,&k,&s)==4) { for(int i=1; i<=k; i++) scanf("%d%d",&a[i],&b[i]); memset(dp,0,sizeof(dp)); int minn=INF; for(int i=1; i<=k; i++) for(int j=b[i]; j<=m; j++) for(int p=1; p<=s; p++) { dp[j][p]=max(dp[j][p],dp[j-b[i]][p-1]+a[i]); if(dp[j][p]>=n && j<minn) minn=j; } if(minn==INF) puts("-1"); else printf("%d\n",m-minn); } return 0; }