一种变种背包问题的动态规划算法

Question

我刚在想,

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

想象一下原始问题,具有各种权重/值的项目.

我的版本将与正常权重/值一起包含"组"值.

例如.Item1 [5kg,$ 600,电子] Item2 [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];
}

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

Answer 1

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