0

我正在阅读有关 0-1 背包问题的维基百科。我只是想澄清几件事。我有两个问题： http ://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_Knapsack_Problem

我遇到了这个伪代码：

// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
for w from 0 to W do
  m[0, w] := 0
end for 
for i from 1 to n do
  for j from 0 to W do
    if j >= w[i] then
      m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])
    else
      m[i, j] := m[i-1, j]
    end if
  end for
end for

专门针对这部分：

    if j >= w[i] then
      m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])

1）如果我错了，请纠正我，但不应该是：

      m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i], m[i,j-w[i]] + v[i])

?

或者如果没有，有人可以解释我为什么不需要它吗？

...

2）我还有另一个问题，如果说我想优化一下。让“for j from 0 to W”循环增加所有项目权重的 GCD（即存储在数组 w 中的值的 GCD）是否明智。（当我即将实现它时，我现在只是在考虑代码方面的问题）。

4

1 回答 1

1

1）当您添加时m[i,j-w[i]] + v[i]，您允许i多次选择相同的项目，因此它不再是 0/1 背包 - 它成为每个项目无限数量的背包问题。

2) 是的，但是这个 GCD 在实际实例中通常会降到 1，因此对于一般情况不值得打扰，除非您事先知道您的数据会从中受益。（在这种情况下，您实际上希望将所有数据除以 GCD，并保持原始算法一次递增 1，然后将最终结果乘以 GCD。这也可以节省内存，但是您的背包容量也必须能被这样的 GCD 整除）

于 2013-05-17T22:43:23.887 回答