一类变型背包问题的形成动态规划算法

Question

我在想，

我想做一个背包问题的变体。

想象最初的问题，项目具有不同的权重/值。

我的版本，除了具有正常的权重/值外，还包含一个"group"值。

。Item1[5公斤，$600，电子]Item2[1公斤，$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];
}

这就是我目前所做的，需要添加它，这样它就会在每次解决这个问题时从它所在的组中删除所有相应的项

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—这种方法可能会导致您的解决方案的性能随着每组中项目数量的增加而不可接受地下降。

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 != {}`