【分析】
二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。
问怎样选择物品可以得到最大的价值。
设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为c[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]]+c[i]}。
如前述方法，可以只使用二维的数组：当每件物品只可以取一次时变量v和u采用逆序的循环，当物品有如完全背包问题时采用顺序的循环。
当物品有如多重背包问题时拆分物品。 物品总个数的限制 有时，“二维费用”的条件是以这样一种隐含的方式给出的：最多只能取M件物品。
这事实上相当于每件物品多了一种“件数”的费用，每个物品的件数费用均为1，可以付出的最大件数费用为M。
换句话说，
设f[v][m]表示付出费用v、最多选m件时可得到的最大价值，则根据物品的类型（01、完全、多重）用不同的方法循环更新，最后在f[0..V][0..M]范围内寻找答案。
【代码】
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; int dp[25][105]; struct no { int y,d,hight; }ss[1005]; int max(int x,int y) { return x>y?x:y; } int main() { int m,n,t; while(~scanf("%d%d",&m,&n)) { memset(dp,127/2,sizeof(dp)); scanf("%d",&t); for(int i=0;i<t;++i) { scanf("%d%d%d",&ss[i].y,&ss[i].d,&ss[i].hight); } dp[0][0]=0; for(int i=0;i<t;++i) { for(int j=m;j>=0;--j)//因为必须达到m和n，所以不用考虑它是不是存在 for(int k=n;k>=0;--k) { int a=j+ss[i].y; if(a>m) a= m; int b = k + ss[i].d; if(b>n) b=n; if(dp[a][b]>dp[j][k]+ss[i].hight)//必须这么写 写成dp[a][b]=max(dp[a][b],dp[j][k]+ss[i].hight)是错的 dp[a][b]=dp[j][k]+ss[i].hight; } } printf("%d\n",dp[m][n]); } return 0; }
