该问题对应于哪种背包问题变体？
让我们想象一下，我必须在约束下装满我的背包：
- 每个物品都有一个相关的重量 wi 和利润 pi
- 最大总重量 Wmax
知道：
- 物品有类别，我必须选择一个物品 从每个类别
- 当然，目标是选择项目来最大化利润总和
示例：Wmax=400
| 书籍 | 书籍重量 | 书籍利润 | 食品 | 食品重量 | 食品利润 |
|---|---|---|---|---|---|
| 圣经 | 500 | 25 | 奶酪 | 80 | 120 |
| 小王子 | 150 | 5 | 香蕉 | 250 | 200 |
这里，最好的解决方案是（小王子，香蕉）
我有一个类似的问题，我想找出最好的编码方式，但我无法弄清楚问题的版本/变体是什么，它是已知的变体吗？
Let us imagine that I have to fill my knapsack with items under constraints:
- Each item has an associated weight wi and profit pi
- With a maximum total weight Wmax
Knowing that:
- There are categories of items and I have to choose exactly one item from each category
- Of course, the aim is to choose items to maximise the sum of the profits
Example : Wmax=400
| Books | Books weights | Books profits | Food | Food weights | Food profits |
|---|---|---|---|---|---|
| The Bible | 500 | 25 | Cheese | 80 | 120 |
| The little prince | 150 | 5 | Banana | 250 | 200 |
Here, the best solution is (The little prince, Banana)
I have a similar problem and I'd like to find out the best way to code it but I can't figure out what version/ variation of the probleme this is, is it a known variation ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我不确定是否存在与您的版本相匹配的现有变体，但很容易从经典变体中得出推论并解决这个问题。
经典变体具有 2D 动态规划（
DP[N][W]，其中N和W是物品数量和最大重量）。在此变体中，由于我们只能选择每个类别中的一个，因此您可以使用 3D DP，例如 dp[i][w][j]，它表示从第一个 < 中可以获得的最大值重量为
w和j的 code>i 项是 0/1 int，表示类别号j中的项是否已被选择与否。我将保留实现，因为递归关系相对简单并且与经典变体非常相似。
I’m not sure if there’s an existing variation that matches yours, but it’s easy to draw inference from the classical variant and solve this.
Classic variant has 2D dynamic programming (
DP[N][W], whereNandWare number of items and max weight).In this variant, since we can only pick one of each category, you can use 3D DP like
dp[i][w][j], which denotes the maximum value you can get from the firstiitems with weightwandjis a 0/1 int denoting whether an item from category numberjhas been selected or not.I’ll leave the implementation, since the recursive relation is relatively simple and quite similar to the classic variant.