题目描述
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
本题考查多重背包的二进制优化方法。
算法1
二进制的优化,是用最少的数,去组成s中所有可能的数。枚举了所有的可能,优化了算法。一维优化的不容易理解,还原成2位数组,进行遍历就ok.
C++ 代码
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int N = 2010;
int n,m;
int f[N];
struct Good{
int v,w;
};
int main(){
vector<Good> goods;
cin>>n>>m;
for(int i=1;i<=n;i++){
int v,w,s;
cin>>v>>w>>s;
for(int k=1;k<=s;k*=2){//将s份划分为小份,最少多少份能够完全组成s,
//如7只需要1,2,4就能组成7以内所有数。(0-7),从s份优化为log2(s),没明白跟这道题k份划分有什么关系
s = s - k;
goods.push_back({v*k,w*k});
}
if(s>0) goods.push_back({v*s,w*s});
}
for(auto good: goods){
for(int j=m;j>=good.v;j--){
f[j] = max(f[j],f[j-good.v] +good.w );
}
}
cout<<f[m]<<endl;
return 0;
}