无界背包的动态规划极小化

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吗？如果没有，有人能提供另一种解决方案或技术来解决这样的问题吗？

谢谢，丹

Answer 1

你会有新的复发

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

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

请注意，对于所有j，DP[i][j]=0

此外，根据DP[i][j]的定义，人们可能期望DP[i][0]的非零值，因为j=0对应于0的最小权重，但DP[i][0]=0对于所有i是DP算法所必需的。