二进制优化多重背包为01背包
#include<iostream>
using namespace std;
const int N = 12000; //小件总数至多数=大件总数最大值*log(si的最大值)+1000(保险)
//从大件总数最大值*si的最大值---->优化为大件总数最大值*log(si的最大值)
int vo[N],va[N],dp[2010];
int main(){
int new_number=0; //0号编号不放有效信息,从1开始
int big,V; cin>>big>>V;
for(int i=1;i<=big;i++){ //对i号大件[即si件物品i]进行处理
int k=1; //将si件物品i拆分为k1,k2..km,C件物品i
//k1=1,k2=1*2,k3=1*2*2,...,C=si-(k1+k2+...+km)
//这样便可以用若干k和C表示出所有0~si之间的所有数据,然后01背包便可以
int vol,val,s; cin>>vol>>val>>s; //记录voi,vai和si
while(k<=s){
new_number++;
vo[new_number]=k*vol; //用一个vo存放当前k件物品i所占用的体积,变成一个小件
va[new_number]=k*val; //用一个va存放当前k件物品i所具有的价值,变成一个小件
s-=k; k=k*2; //si要减去之前的k,用来算当前k后面的k以及C
}
if(s>0){ //此时的s便是C
new_number++;
vo[new_number]=s*vol;
va[new_number]=s*val;
}
}
int small=new_number; //小件总数
for(int i=1;i<=small;i++){ //对small件商品进行01背包
for(int v=V;v>=vo[i];v--){
dp[v]=max(dp[v],dp[v-vo[i]]+va[i]);
}
}
cout<<dp[V]; return 0;
}
```