多重背包问题(限制其物品的个数,介于无限和唯一之间)
一种方法是压入k个物品i,转变成01背包问题,但是还可以简化一下,
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}
,这样一来就可以简化为完全背包问题的方法,path[][]长度得到压缩。
for(j=weight[i];j<=volumn;j++){ // 需要重叠,所以从左到右
for(k=1;k<=j/weight[i];k++){
if(dp[j-k*weight[i]]+k*value[i]>dp[j]){
path[i][j]=1;
dp[j]=dp[j-k*weight[i]]+k*value[i];
}
}
}
网友评论