多重背包问题II—数据量增加的二进制优化方案
思想:本质上还是多重背包问题I中的,对于每种物品有s+1个子集,但是由于这里s的数据量过大,如果再划分为s+1个就会超时了
这里用到二进制来表示
【例如】
假设一件物品有7件,那么如果没有二进制的话,就是7+1=8个选择(选0个,1个,…,7个)
如果引入了二进制,我只需要用3+1=4个选择就能表示出这8个子集:
0=0
1=1
2=2
3=1+2
4=4
5=1+4
6=2+4
7=1+2+4
即,只用了1,2,4这三个数表示了,这样就能很大程度上进行优化
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int n,m;
const int N = 2010;
const int M = 11010;//最大会有约为1000*11项
int dp[N];
int volume[M],value[M];
int cnt=0;
int main(){
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){
cnt+=1;
volume[cnt]=k*v;
value[cnt]=k*w;
s-=k;
}
if(s>0){
cnt+=1;
volume[cnt]=s*v;
value[cnt]=s*w;
}
}
for(int i=1;i<=cnt;i++){
for(int j=m;j>=volume[i];j--){
dp[j]=max(dp[j],dp[j-volume[i]]+value[i]);
}
}
cout<<dp[m];
}