限制背包解决方案中每个项目的数量
Limiting number of each item in knapsack solution
我试图更好地理解背包问题，并且正在查看此处给出的 "Specific Dynamic Programming solution"：
http://rosettacode.org/wiki/Knapsack_Problem/Python
我想对其进行修改，以便在解决方案中最多可以使用 items 中的每一项。我认为这可以通过循环遍历重量和体积之外的项目来完成，但这没有用。
感谢任何帮助。
编辑：
例子：
目前代码定义了一个项目列表
items = [Bounty('panacea', 3000, 3, 25),
Bounty('ichor', 1800, 2, 15),
Bounty('gold', 2500, 20, 2)]
它选择小于背包重量和体积限制的物品的最大值组合，并允许每个物品多次使用。
我希望它选择重量和价值 < 背包的重量和体积限制的物品的最大值组合，但限制是项目中的每个项目最多只能使用一次。
正如我在评论中提到的，您可以使用 O(n * W) 动态规划方法，其中 n 是物品数量， W 是背包的容量。更多详情请参考这里：
https://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_knapsack_problem
如果 W 足够小，该算法非常容易实现并且非常快。
如果你想防止每个项目被多次使用：
1) 使 DP 算法减少而不是增加+首先处理每个项目而不是先循环重量和体积
这样每一项就不能多次计数了。
并且通过首先循环项目，您不会错过项目组合的机会。
例如，当您的 table 为空并且您处理了第一个项目。它将采取当前最好的和最好的位置 [w-weight][v-volume]+value
table[w][v] = max(table[w][v], table[w - item.weight][v - item.volume] + item.value)
所以对于灵丹妙药:
当您按递增顺序进行时，table[25][3] 将在处理 table[50][6] 时变为 3000。制作6000，使用2次
当您按降序排列时，table[25][3] 在处理 table[50][6] 时仍将是 0。打3000只用一次
因此，无论 table 值较低的是什么，都不会来自同一项目。
2) 检查所有物品何时适合背包
顺便说一下，当所有物品都适合背包时，这确实会崩溃。
你可以重写这个或者简单地在方法的开头添加一个检查：
def knapsack_dp(items, sack):
if(sum(item.weight for item in items) <= sack.weight
and sum(item.volume for item in items) <= sack.volume):
return [1] * len(items)
当它完全适合时，return 所有项目。
我试图更好地理解背包问题，并且正在查看此处给出的 "Specific Dynamic Programming solution"： http://rosettacode.org/wiki/Knapsack_Problem/Python
我想对其进行修改，以便在解决方案中最多可以使用 items 中的每一项。我认为这可以通过循环遍历重量和体积之外的项目来完成，但这没有用。
感谢任何帮助。
编辑： 例子： 目前代码定义了一个项目列表
items = [Bounty('panacea', 3000, 3, 25),
Bounty('ichor', 1800, 2, 15),
Bounty('gold', 2500, 20, 2)]
它选择小于背包重量和体积限制的物品的最大值组合，并允许每个物品多次使用。
我希望它选择重量和价值 < 背包的重量和体积限制的物品的最大值组合，但限制是项目中的每个项目最多只能使用一次。
正如我在评论中提到的，您可以使用 O(n * W) 动态规划方法，其中 n 是物品数量， W 是背包的容量。更多详情请参考这里：
https://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_knapsack_problem
如果 W 足够小，该算法非常容易实现并且非常快。
如果你想防止每个项目被多次使用：
1) 使 DP 算法减少而不是增加+首先处理每个项目而不是先循环重量和体积
这样每一项就不能多次计数了。
并且通过首先循环项目，您不会错过项目组合的机会。
例如，当您的 table 为空并且您处理了第一个项目。它将采取当前最好的和最好的位置 [w-weight][v-volume]+value
table[w][v] = max(table[w][v], table[w - item.weight][v - item.volume] + item.value)
所以对于灵丹妙药:
当您按递增顺序进行时，
table[25][3]将在处理table[50][6]时变为3000。制作6000，使用2次当您按降序排列时，
table[25][3]在处理table[50][6]时仍将是0。打3000只用一次
因此，无论 table 值较低的是什么，都不会来自同一项目。
2) 检查所有物品何时适合背包
顺便说一下，当所有物品都适合背包时，这确实会崩溃。
你可以重写这个或者简单地在方法的开头添加一个检查：
def knapsack_dp(items, sack):
if(sum(item.weight for item in items) <= sack.weight
and sum(item.volume for item in items) <= sack.volume):
return [1] * len(items)
当它完全适合时，return 所有项目。