传送门啦
这个题就快好多,这次打的代码相比较旅行商的背包,我用了预处理,先处理成01背包,然后直接dp。
没有在dp中进行,可能会快一点吧。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e4 * 4 + 5;
inline int read(){
char ch = getchar();
int f = 1 , x = 0;
while(ch > '9' || ch < '0'){if(ch == '-')f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + ch - '0';ch = getchar();}
return x * f;
}
int n,c,v,w,m,tot;
long long value[maxn],size[maxn],f[maxn];
int main(){
n = read(); c = read();
for(int i=1;i<=n;i++){
v = read(); w = read(); m = read();
for(int k=1;k<=m;k<<=1){
value[++tot] = k * v;
size[tot] = k * w;
m -= k;
}
if(m > 0){
value[++tot] = m * v;
size[tot] = m * w;
}
}
for(int i=1;i<=tot;i++)
for(int j=c;j>=size[i];j--)
f[j] = max(f[j] , f[j-size[i]] + value[i]);
printf("%lld",f[c]);
return 0;
}