形成背景问题变化的动态规划算法

所以我在想，形成背景问题变化的动态规划算法

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

想象一下原来的问题，具有不同重量/价值的物品。

我的版本将与正常的权重/值一起包含“组”值。

例如。项目1 [5KG，$ 600电子] 项目2 [1KG，$ 50食品]

现在，有一组这样的项目，我将如何编写了背包问题，以确保从最多1项选择每个“组”。

注：

你并不需要从该组中选择一个项目
有各组
你还在重量最小化在多个项目，实现价值最大化
的预定义的组的数量以及它们的值。

我只是在这个阶段写了一个代码草稿，而且我选择了使用动态方法。我理解常规背包问题的动态解决方案背后的想法，我如何改变这个解决方案以合并这些“组”？

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]; 
}

这是我到目前为止，需要补充它，这样它会删除它是每一个它解决了这次在组中的所有相关项目。

来源

2011-10-07 user730882

将群组项添加到状态！ – quasiverse

解决它作为一个组合优化问题呢？对于每件商品，您可以选择一件商品或者不选择商品。您可能想使用分支和界限搜索来解决它。 – ysdx

假设
C [1]：第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-09 16:28:27 gibraltar

刚刚注意到你的问题，试图找到我自己的问题的答案。你所说的问题是一个众所周知的，被广泛研究的问题，称为多重选择背包问题。如果你google了，你会发现各种各样的信息，我也可以推荐这本书：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-16 12:25:23 Karen

形成背景问题变化的动态规划算法

回答

相关问题