为变形的背包问题构建动态规划算法

Question

我在思考，

我想要对背包问题进行变体。

假设有原始问题，其中包含具有不同重量/价值的物品。

我的版本将与正常的重量/价值一起，包含一个“组”值。

例如：物品1 [5kg，$600，电子产品] 物品2 [1kg，$50，食品]

现在，有了这样一组物品，如何编写背包问题的代码，以确保仅选中每个“组”中的最多1个物品。

注意：

1. 您不需要从该组中选择任何物品
2. 每个组中有多个物品
3. 您仍要最小化重量，最大化价值
4. 组的数量是预定义的，以及它们的值。

此时我只是草拟出代码，并且选择使用动态方法。我了解常规背包问题的动态解决方案的想法，如何修改此解决方案以包含这些“组”？

KnapSackVariation(v,w,g,n,W)
{
  for (w = 0 to W)
     V[0,w] = 0;
  for(i = 1 to n)
     for(w = 0 to W)
        if(w[i] <= w)
           V[i,w] = max{V[i-1, w], v[i] + V[i-1, w-w[i]]};
        else
           V[i,w] = V[i-1, w];
     return V[n,W];
}

这是我目前的成果，需要添加代码以便在解决问题时删除该组中的所有相应项目。

- user730882

---

将一个组项添加到状态中！ - flight

将其视为组合优化问题来解决怎么样？对于每个项目，您可以选择一个项目或不选。您可能希望使用分支定界搜索来解决它。 - ysdx

Answer 1

我刚注意到你的问题，正试图找到自己问题的答案。你提出的问题是一个众所周知和深入研究的问题，称为多重选择背包问题。如果你在谷歌上搜索，你会发现各种信息，我还可以推荐这本书：http://www.amazon.co.uk/Knapsack-Problems-Hans-Kellerer/dp/3642073115/ref=sr_1_1?ie=UTF8&qid=1318767496&sr=8-1，其中专门有一章讲述了该问题。在MCKP的经典公式中，你必须从每个组中选择一个项目。然而，你可以通过向每个组添加一个利润和重量均为0的虚拟项来轻松转换成你的版本，并且相同的算法也会起作用。我建议你不要尝试将二进制背包问题的代码调整为带有几个小变化的MCKP——这种方法可能会导致你的解决方案的性能随着每个组中物品数量的增加而不可接受地降低。

- Karen

Answer 2

假设
c[i]：第i个元素的类别
V[i，w，S]：背包最大价值，使其包含S中每个类别的最多一个物品

Recursive Formulation
V[i,w,S] = max(V[i-1,w,S],V[i,w-w[i],S-{c[i]}] + v[i])
Base Case
V[0,w,S] = -`infinity if w!=0 or S != {}`

- gibraltar