algorithm - 这个问题对应于哪个背包问题变体？

Question

让我们想象一下，我必须在限制条件下用元素装满我的背包:

• 每个项目都有一个关联的权重 wi 和利润 pi
• 最大总重量Wmax

知道:

• 有项目类别，我必须从每个类别中选择恰好一个项目
• 当然，选择项目的目的是最大化利润的总和

例子:Wmax=400

<表类="s-表"> <头> 书籍 书本重量 图书利润 食物 食物重量 食品利润 <正文> 圣经 500 25 奶酪 80 120 小王子 150 5 香蕉 250 200

这里，最好的解决方案是(小王子，香蕉)

我有一个类似的问题，我想找到最好的编码方式，但我不知道这是什么版本/变体，它是已知变体吗？

Answer 1

我不确定是否存在与您的匹配的现有变体，但很容易从经典变体中得出推论并解决这个问题。

经典变体具有 2D 动态规划(DP[N][W]，其中 N 和 W 是项目数和最大重量).

在这个变体中，由于我们只能从每个类别中选择一个，您可以使用像 dp[i][w][j] 这样的 3D DP，它表示您可以从中获得的最大值权重为 w 和 j 的第一个 i 项是一个 0/​​1 整数，表示是否来自类别编号 j 是否被选中。

我将离开实现，因为递归关系相对简单并且与经典变体非常相似。