题目描述
二维费用的背包问题
二维费用背包问题就是比一维费用背包问题多了一层的要求 总体思想不变
这道题是01背包问题的二维问题 多了一层重量的限制
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N1 =1010;
const int N2 =110;
int v[N1], m[N1], w[N1];
int f[N1][N2][N2];
int n,V,M;
int main()
{
cin>>n>>V>>M;
for(int i=1;i<=n;i++)
cin>>v[i]>>m[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=0;j<=V;j++)
for(int k=0;k<=M;k++)
{
if(v[i]>j||m[i]>k) f[i][j][k]=f[i-1][j][k];
else
{
f[i][j][k]=max(f[i-1][j][k],f[i-1][j-v[i]][k-m[i]]+w[i]);
}
}
cout<<f[n][V][M]<<endl;
return 0;
}