5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
249
【分析】
二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。
问怎样选择物品可以得到最大的价值。
设这两种代价分别为代价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;
}