这个问题对应于哪个背包问题变体？
To which Knapsack-problem variation does this problem correspond?
让我们想象一下，我必须在限制条件下用物品装满我的背包：
- 每个项目都有关联的权重 wi 和利润 pi
- 最大总重量Wmax
知道：
- 有项目类别，我必须从每个类别中选择恰好一个项目
- 当然，选择项目的目的是最大化利润总和
示例：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
这里，最好的解决方案是（小王子，香蕉）
我有一个类似的问题，我想找出最好的编码方式，但我不知道这是什么版本/变体，它是已知的吗变化 ?
我不确定是否有与你的匹配的现有变体，但很容易从经典变体中得出推论并解决这个问题。
经典变体具有二维动态规划（DP[N][W]，其中 N 和 W 是项目数和最大重量）。
在这个变体中，由于我们只能从每个类别中选择一个，您可以使用像 dp[i][w][j] 这样的 3D DP，它表示您可以从具有权重的前 i 个项目中获得的最大值w 和 j 是一个 0/1 整数，表示是否选择了类别编号 j 中的项目。
我会离开实现，因为递归关系相对简单并且与经典变体非常相似。
让我们想象一下，我必须在限制条件下用物品装满我的背包：
- 每个项目都有关联的权重 wi 和利润 pi
- 最大总重量Wmax
知道：
- 有项目类别，我必须从每个类别中选择恰好一个项目
- 当然，选择项目的目的是最大化利润总和
示例：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 |
这里，最好的解决方案是（小王子，香蕉）
我有一个类似的问题，我想找出最好的编码方式，但我不知道这是什么版本/变体，它是已知的吗变化 ?
我不确定是否有与你的匹配的现有变体，但很容易从经典变体中得出推论并解决这个问题。
经典变体具有二维动态规划（DP[N][W]，其中 N 和 W 是项目数和最大重量）。
在这个变体中，由于我们只能从每个类别中选择一个，您可以使用像 dp[i][w][j] 这样的 3D DP，它表示您可以从具有权重的前 i 个项目中获得的最大值w 和 j 是一个 0/1 整数，表示是否选择了类别编号 j 中的项目。
我会离开实现，因为递归关系相对简单并且与经典变体非常相似。