题目描述
有 N 种物品和一个容量是 V 的背包。
物品一共有三类:
第一类物品只能用1次(01背包);
第二类物品可以用无限次(完全背包);
第三类物品最多只能用 si 次(多重背包);
每种体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。
si=−1 表示第 i 种物品只能用1次;
si=0 表示第 i 种物品可以用无限次;
si>0 表示第 i 种物品可以使用 si 次;
输出格式
输出一个整数,表示最大价值。
思路
对于混合背后问题,通过判断,将其分为不同的背包进行求解。
01背包问题的状态方程跟不完全背包问题相同。
最后就分为两类:
1.01背包问题+不完全背包问题(不完全背包问题,用二进制划分进行优化)
2.完全背包问题
C++ 代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N=1010;
int m,v;
int f[N];
struct Good{
int kind;
int v,w;
};
int main(){
cin>>m>>v;
vector<Good> goods;
for(int i=0;i<m;i++){
int n,w,s;
cin>>n>>w>>s;
if(s<0){
goods.push_back({-1,n,w});//01背包
}
else if(s==0){
goods.push_back({0,n,w});//完全背包
}
else{
for(int k=1;k<=s;k*=2){
s = s - k;
goods.push_back({-1,n*k,w*k});//不完全背包,二进制划分,01背包变形
}
if(s>0) goods.push_back({-1,n*s,w*s});
}
}
for(auto good: goods){
if(good.kind<0){
for(int j=v;j>=good.v;j--) f[j] = max(f[j], f[j - good.v] + good.w);//01背包
}
else{
for(int j=good.v;j<=v;j++) f[j] = max(f[j], f[j - good.v] + good.w);//完全背包
}
}
cout<<f[v]<<endl;
return 0;
}