形成背包问题变体的动态规划算法
我在想，
我想对背包问题做一个变体。
想象一下最初的问题，其中的物品具有不同的重量/价值。
我的版本除了具有正常的权重/值外，还将包含一个“组”值。
例如。 商品1[5公斤，600美元，电子] Item2[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];
}
这就是我到目前为止所拥有的，需要添加它，以便每次解决这个问题时都会从它所在的组中删除所有相应的项目。
I was thinking,
I wanted to do a variation on the Knapsack Problem.
Imagine the original problem, with items with various weights/value.
My version will, along with having the normal weights/values, contain a "group" value.
eg.
Item1[5kg, $600, electronic]
Item2[1kg, $50, food]
Now, having a set of items like this, how would I code up the knapsack problem to make sure that a maximum of 1 item from each "group" is selected.
Notes:
- You don't need to choose an item from that group
- There are multiple items in each group
- You're still minimizing weight, maximizing value
- The amount of groups are predefined, along with their values.
I'm just writing a draft of the code out at this stage, and I've chosen to use a dynamic approach. I understand the idea behind the dynamic solution for the regular knapsack problem, how do I alter this solution to incorporate these "groups"?
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];
}
That's what I have so far, need to add it so that it will remove all corresponding items from the group it is in each time it solves this.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
刚刚注意到你的问题试图找到我自己问题的答案。您所说的问题是一个众所周知且经过深入研究的问题，称为“多项选择背包问题”。如果你用谷歌搜索，你会找到各种各样的信息，我也可以推荐这本书：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——这种方法可能会导致您得到一个解决方案，其性能随着每组中的项目数量的增加而下降得令人无法接受。
just noticed your question trying to find an answer to a question of my own. The problem you've stated is a well-known and well-studied problem called the Multiple Choice Knapsack Problem. If you google that you'll find all sorts of information, and I can also recommend this book: http://www.amazon.co.uk/Knapsack-Problems-Hans-Kellerer/dp/3642073115/ref=sr_1_1?ie=UTF8&qid=1318767496&sr=8-1, which dedicates a whole chapter to the problem. In the classic formulation of MCKP, you have to choose one item from each group. However, you can easily convert that version of the problem to your version by adding a dummy item to each group with profit and weight = 0, and the same algorithms will work. I would caution you against trying to adapt code for the binary knapsack problem to the MCKP with a few tweaks--this approach is likely to lead you to a solution whose performance degrades unacceptably as the number of items in each group increases.
假设
c[i]：第i个元素的类别
V[i,w,S] ：背包的最大值，使其最多包含 S 中每个类别的一项
Assume
c[i] : The category of the ith element
V[i,w,S] : Maximum value of the knapsack such that it contains at max one item from each category in S