您好,欢迎来到二三娱乐。
搜索
您的当前位置:首页多重背包问题

多重背包问题

来源:二三娱乐

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

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

Copyright © 2019- yule263.com 版权所有 湘ICP备2023023988号-1

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务