java - 了解解决资源分配问题的子集总和

Question

我在互联网上找到了这段代码，但我很难理解它。谁能给出一些解释，这将非常有帮助。

  SubsetSum(n, W):
Initialize M[0,w] = 0 for each w = 0,...,W
Initialize M[i,0] = 0 for each i = 1,...,n
For i = 1,...,n: for every row
For w = 0,...,W: for every column
If w[i] > w: case where item can’t fit
  M[i,w] = M[i-1,w]

M[i,w] = max( which is best?
M[i-1,w],
w[j] + M[i-1, W-w[j]]
)
Return M[n,W]

Answer 1

分类

这是Dynamic Programming的典型应用.

变量

令 w[i] 表示项目 i 的重量，W 表示全局容量，M[i,w] 使用前 i 个对象和剩余容量 w 的子集求和问题的最优解。

重点观察

要从先前的值 M[i-1,*] 获得最优解 M[i,w]，我们可以包含下一项 我 或离开它。如果我们包含项目 i，则 M[i,w] = w[i] + M[i-1, w-w[i]](添加权重 w[i] 用于包含项目 i，但将剩余容量减少相同数量；涉及 j 的幻灯片上有错字) .如果我们将项目 i 排除在外，则 M[i,w] = M[i-1,w](不向先前的解决方案添加任何值并保持相同剩余容量)。

我们对最优(最大)解感兴趣，因此我们取这两个值中的最大值。无论如何，我们已经减少了 M[i,*] 的索引。这意味着，如果我们知道值 M[i',*]，我们可以为 i > i'< 计算值 M[i,*]/。这正是动态编程的理念。

注意

第一行是初始化，在值w[i]大于剩余容量w的情况下，我们显然可以不包含项目我。返回值 M[n,W] 描述了包含以全局容量开头的所有项目的最佳解决方案。