美文网首页
多重背包问题

多重背包问题

作者: 小幸运Q | 来源:发表于2019-01-03 15:26 被阅读0次

    多重背包问题(限制其物品的个数,介于无限和唯一之间)

    一种方法是压入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];
                         }
                }
            }
    

    相关文章

      网友评论

          本文标题:多重背包问题

          本文链接:https://www.haomeiwen.com/subject/lynfrqtx.html