题目描述
多重背包问题。
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
样例
01背包的变形,在考虑01背包的时候,多一个循环,将0-k个同样物体进行选取判断。
算法1
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int m,v;
int M[N],V[N],S[N];
int f[N][N];
int main(){
cin>>m>>v;
for(int i=1;i<=m;i++){
cin>>M[i]>>V[i]>>S[i];
}
for(int i=1;i<=m;i++){
for(int j=0;j<=v;j++){
for(int k=0;k<=S[i];k++){
if(j>=k*M[i]){
f[i][j] = max(f[i][j], f[i-1][j-k*M[i]] + k*V[i]);
}
}
}
}
cout<<f[m][v]<<endl;
return 0;
}
算法2
空间优化,同01背包优化一样
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int m,v;
int M[N],V[N],S[N];
int f[N];
int main(){
cin>>m>>v;
for(int i=1;i<=m;i++){
cin>>M[i]>>V[i]>>S[i];
}
for(int i=1;i<=m;i++){
for(int j=v;j>=M[i];j--){
for(int k=0;k<=S[i];k++){
if(j>=k*M[i]){
f[j] = max(f[j], f[j-k*M[i]] + k*V[i]);
}
}
}
}
cout<<f[v]<<endl;
return 0;
}