动态规划最小化背包

Question

我很好奇是否有可能修改（或使用）无限制背包问题的DP算法，以使背包中物品的总价值最小化，同时使总重量至少达到一些最小约束C。

---

自底向上的DP算法，用于UKP的最大化版本：

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最小化吗？如果没有，谁能提供其他解决方案或技术来解决这样的问题？

谢谢，丹

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物品的最小值。应该是一些足够大的值，使得任何合法值都小于。0..i-1jinfinityinfinity