’‘’
include[HTML_REMOVED]
/*
将多重背包问题转化为01背包问题
假设某个物品一共有s个 可以将它划分成 1 , 2^1 , 2^2....c c<2^(k+1)
然后放到 价值 和 体积 数组里面 将它化作01背包问题考虑
/
using namespace std;
const int N=25000;
int v[N],w[N],f[N],n,m;
int main(){
cin>>n>>m;
int cnt=0;
for(int i=1;i<=n;i){
int a,b,s;
cin>>a>>b>>s;
int k=1;
while(k<=s){
cnt;
v[cnt]=ak;
w[cnt]=bk;
s-=k;
k=2;
}
if(s>0){
cnt++;
v[cnt]=sa;
w[cnt]=sb;
}
}
n=cnt;
for(int i=1;i<=n;i++){
for(int j=m;j>=v[i];j--){
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m];
}
’‘’