关于本节无限量物品背包问题的一些疑问
来源：9-6 0-1背包问题的优化和变种
Flight0
2017-06-20
当所选物品的数量并无限制之时，使用贪心算法是否能够得到最优的解法，每次都使用单位质量价值最大的物品，直到将背包装满。当使用动态规划的思想实现的时候是否可以从背包重量递增的角度进行考虑而非从选择物品的角度进行考虑。以下是我的动态规划代码，谢谢老师
def max_package(weight, value, package_weight): memo = [0] n = len(weight) for size in range(1, package_weight + 1): max_value = 0 for index in range(0, n): if (weight[index] <= size): max_value = max(max_value, value[index] + memo[size - weight[index]]) memo.append(max_value) return memo[package_weight]
写回答
1回答
-
贪心算法是不可以的。所选物品的多少并不能改变背包问题本身的性质。
比如如下反例：
物品1： 重量10 价值50 （单位价值5） 数量：无限个
物品2： 重量3 价值14（单位价值<5） 数量：无限个
背包容量：12
如果使用贪心算法，只能放进1个物品1，背包总价值为50；但是最优解是放入4个物品2，背包总价值是14*4=56。
----------
你的动态规划代码我没有仔细验证。但是看上去大体思路是正确的。其实本质是双重循环先遍历哪一个变量的问题，其中状态的定义和转移方式并没有改变。所谓同样的算法思路，是有多种实现方式的：）非常赞的思考！
加油！
012017-06-20
相似问题