使用动态规划优化无界背包问题

Question

我想知道是否有可能修改（或使用）无界背包问题的DP算法，以使背包中物品的总价值最小化，同时使总重量至少为某个最小约束C。

---

UKP最大化问题的自底向上DP算法：

let w = set of weights (0-indexed)

and v = set of values (0-indexed)

    DP[i][j] = max{ DP[i-1][j], DP[i][j - w[i-1]] + v[i-1] }

for i = 0,...,N and j = 0,...,C

given DP[0][j] = 0 and DP[i][0] = 0

where N = amount of items

and C = maximum weight

DP[N][C] = the maximum value of items for a knapsack capacity of C 

---

我们能否制作一个最小化UKP？如果不行，是否有其他解决此类问题的方法或技术？

谢谢，丹

- danrpts

---

请注意，在上述算法中是DP[i-1][j - w[i-1]]，而不是DP[i][j - w[i-1]]。我尝试进行了更改，但审核没有通过。 - bernie

Answer 1

您将拥有新的循环发生。

DP[i][j] (i = 0, j = 0) = 0
DP[i][j] (i = 0, j > 0) = infinity
DP[i][j] (i > 0       ) = min{ DP[i-1][j], DP[i-1][max(0, j - w[i-1])] + v[i-1] },

对于每个 i 和 j，它给出了使重量至少为 j 时项目 0..i-1 的最小值。 无穷大 应该是足够大的值，以便任何合法值都小于 无穷大。

- David Eisenstat

---

这个算法能否被修改以适应每种物品数量的无限制？ - rts

@RomanTsopin 将 DP[i-1][j - w[i-1]] + v[i-1] 更改为 DP[i][j - w[i-1]] + v[i-1]。 - David Eisenstat

让我先说明一下：我正在学习DP，还不是最好的，所以请谅解我的错误。我认为这个递归式略微有些偏差。当我运行计算时遇到的一个问题是，如果项目按重量从低到高排序，则无法正确计算。我通过更改你的规则来纠正了这一点。在第二段中，使用索引j-w[-1]将产生负值。如果发生这种情况，我会将它设置为无限而不是零。这样可以使一个重量较轻的物品仍然被包含在集合中。 - Matthew

@DavidEisenstat 当然可以。我已经给您发送了一封附带它的电子邮件。 - Matthew

@Matthew 啊，问题在于“背包”这个词是一个误称，因为问题中没有总重量的上限，只有下限。如果 j < w[i-1]（在你发给我的代码中是 votes[i] > j），那么我们仍然需要考虑取这个物品。我很快就会编辑递归，使其更易于实现。 - David Eisenstat