以下两份代码
AC:
int l=d[u]-1;
rep(j,c[u],m){
f[i][j]=f[i+1][j-c[u]]+w[u];
}
for(int j=1;j<=l;l-=j,j<<=1){
rep(k,c[u]*j,m){
g[i][k]=max(f[i][k],f[i][k-c[u]*j]+w[u]*j);
}
rep(k,c[u]*j,m){
f[i][k]=g[i][k];
}
}
rep(j,c[u]*l,m){
g[i][j]=max(f[i][j],f[i][j-c[u]*l]+w[u]*l);
}
rep(j,c[u]*l,m){
f[i][j]=g[i][j];
}
WA:
int l=d[u];
for(int j=1;j<=l;l-=j,j<<=1){
rep(k,c[u]*j,m){
f[i][k]=max(f[i][k],f[i+1][k-c[u]*j]+w[u]*j);
}
}
if(l){
rep(j,c[u]*l,m){
f[i][j]=max(f[i][j],f[i+1][j-c[u]*l]+w[u]*l);
}
}
都强制选了一个物品,为什么结果不同?