我刚在想,
我想对背包问题做一个变体。
想象一下最初的问题,具有不同权重/值的项目。
我的版本除了具有正常的权重/值外,还包含一个“组”值。
例如。项目 1[5 公斤,600 美元,电子产品] 项目 2 [1 公斤,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];
}
这就是我到目前为止所拥有的,需要添加它,以便它每次解决这个问题时都会从它所在的组中删除所有相应的项目。