algorithm - 形成背包问题变体的动态规划算法

Question

我在想，

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

想象一下原始问题，元素具有不同的重量/值(value)。

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

例如。Item1[5kg, $600, electronic]Item2[1kg, $50, 食物]

现在，有了一组这样的元素，我该如何编写背包问题的代码以确保从每个“组”中最多选择 1 件元素。

注意事项:

1. 您不需要从该组中选择一个项目
2. 每组有多个项目
3. 您仍然在减轻重量，使值(value)最大化
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——这种方法可能会导致您的解决方案随着每组中项目数量的增加而性能下降到 Not Acceptable 程度。