AcWing 7. 混合背包问题
原题链接
中等
作者:
向阳而生_J
,
2024-05-02 09:19:40
,
所有人可见
,
阅读 2
C++ 代码
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N=1010;
int n,m;
int f[N];
void solve(){
cin>>n>>m;
for(int i=0;i<n;i++){
int v,w,s;
cin>>v>>w>>s;
if(s==0){//完全背包问题
for(int j=v;j<=m;j++) f[j]=max(f[j],f[j-v]+w);
}
else{
if(s==-1)s=1;
for(int k=1;k<=s;k*=2){
for(int j=m;j>=k*v;j--){
f[j]=max(f[j],f[j-k*v]+k*w);
}
s-=k;
}
if(s){
for(int j=m;j>=s*v;j--){
f[j]=max(f[j],f[j-s*v]+s*w);
}
}
}
}
cout<<f[m]<<endl;
return ;
}
int main(){
IOS
solve();
}