让我们想象一下，在约束条件下，我必须在背包里装满物品：
- 每个项目都有一个相关的权重wi和利润pi
- 最大总重量Wmax
知道：
- 有项目类别，我必须从每个类别中选择一个项目
- 当然，目的是选择最大化利润总额的项目
示例：Wmax=400
| 书籍 | 书籍利润 | 食物食物重量 | >食物利润|
|---|---|---|---|
| 圣经小王子 |
我不确定是否有与您的变体匹配的现有变体，但从经典变体中推断并解决这个问题很容易。
经典变体具有2D动态编程(DP[N][W]，其中N和W是项目数和最大权重(。
在这个变体中，由于我们只能从每个类别中选择一个，因此您可以使用类似dp[i][w][j]的3D DP，它表示您可以从权重为w的第一个i项目中获得的最大值，而j是0/1 int，表示类别号为j的项目是否已被选择。
我将离开实现，因为递归关系相对简单，并且与经典变体非常相似。