6

我刚在想，

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

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

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

例如。项目 1[5 公斤，600 美元，电子产品] 项目 2 [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];
}

这就是我到目前为止所拥有的，需要添加它，以便它每次解决这个问题时都会从它所在的组中删除所有相应的项目。

4

2 回答 2

3

刚刚注意到你的问题试图找到我自己的问题的答案。您所说的问题是一个众所周知且经过充分研究的问题，称为多项选择背包问题。如果你谷歌你会找到各种各样的信息，我也可以推荐这本书：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——这种方法很可能会导致您找到一个解决方案，其性能随着每组中项目数量的增加而下降到无法接受的程度。

于 2011-10-16T12:25:23.043 回答
0

假设
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 != {}`
于 2011-10-09T16:28:27.407 回答