要求从多组中各选择一件的背包

Question

我了解了基本的0-1背包问题及其解决方案。我试图通过 0-1 问题的变体进行推理，其中您不能从单个列表中选择任何项目组合，而是必须从许多不同项目集中分别选择一个项目。

例如，在我的问题中，项目列表如下所示：

食物

• 香蕉（重量9，价值10）
• 面包（重量3，价值25）
• 苹果（重量4，价值30）
• ...

衬衫

• T恤（重量2，价值20）
• 系扣衬衫（重量 3，价值 25）
• ...

裤子

• 卡其裤（重量4，价值30）
• 牛仔裤（重量2，价值30）
• ...

依此类推，问题要求您从食物中精确选择一件商品，从衬衫中选择一件商品，从裤子中选择一件商品，依此类推。

我认为有一个从 Rosetta 代码修改而来的强力解决方案，并且似乎可以工作（如下），但我无法弄清楚如何创建更有效的动态编程解决方案。谁能帮助或指出我正确的方向？我会很感激。

from itertools import product

def anycomb(item1, item2, item3, item4):
    return ( comb
             for comb in product(item1, item2, item3, item4)
             )

def totalvalue(comb):
    ' Totalise a particular combination of items'
    totwt = totval = 0
    for item, wt, val in comb:
        totwt  += wt
        totval += val
    return (totval, -totwt) if totwt <= 400 else (0, 0)

itemset_1 = (
    ("map", 9, 150), ("compass", 13, 35), ("water", 153, 200), ("sandwich", 50, 160),
    ("glucose", 15, 60))
itemset_2 = (
    ("tin", 68, 45), ("banana", 27, 60), ("apple", 39, 40),
    ("cheese", 23, 30), ("suntan cream", 11, 70))
itemset_3 = (
    ("beer", 52, 10), ("camera", 32, 30),
    ("t-shirt", 24, 15), ("trousers", 48, 10), ("umbrella", 73, 40),
    ("waterproof trousers", 42, 70))
itemset_4 = (
    ("waterproof overclothes", 43, 75),
    ("note-case", 22, 80), ("sunglasses", 7, 20), ("towel", 18, 12),
    ("socks", 4, 50), ("book", 30, 10))

bagged = max( anycomb(itemset_1, itemset_2, itemset_3, itemset_4), key=totalvalue) # max val or min wt if values equal
print("Bagged the following items\n  " +
      '\n  '.join(sorted(item for item,_,_ in bagged)))
val, wt = totalvalue(bagged)
print("for a total value of %i and a total weight of %i" % (val, -wt))

Answer 1

您可以使用基本的 0-1 背包问题的解决方案，稍作修改即可。当您选择选择一个项目时，您必须转到上一组的最后一个项目。它的意思是 ：

F(i,w) = max[ F(i-1 , w) , F(A[i]-1 , ww[i]) + P[i] ]

其中 A[i] 表示第 i 项所属的集合中第一项的索引。