题目描述
有 N 件物品和一个容量是 V 的背包,背包能承受的最大重量是 M。
每件物品只能用一次。体积是 vi,重量是 mi,价值是 wi。
求解将哪些物品装入背包,可使物品总体积不超过背包容量,总重量不超过背包可承受的最大重量,且价值总和最大。
输出最大价值。
输入格式
第一行两个整数,N,V,M,用空格隔开,分别表示物品件数、背包容积和背包可承受的最大重量。
接下来有 N 行,每行三个整数 vi,mi,wi,用空格隔开,分别表示第 i 件物品的体积、重量和价值。
输出格式
输出一个整数,表示最大价值。
思路
双重限制的二维01背包问题,增加一个对质量枚举的循环就行。
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int C = 1010;
int n,v,m;
int V[C],M[C],W[C];
int f[C][C];
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=v;j>=V[i];j--){
for(int k=m;k>=M[i];k--){
f[j][k] = max(f[j][k],f[j-V[i]][k-M[i]] + W[i]);
}
}
}
cout<<f[v][m]<<endl;
return 0;
}