无界背包

Question

我需要为我的家庭作业修改wiki的背包伪码，这样它就可以检查你是否能在背包中达到精确的重量W。物品的数量是无限的，而你的价值并不重要。我正在考虑在j>-Wj下添加一个while循环，以检查它适合多少相同的项。那能行吗？

谢谢

// 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

Answer 1

如果我没有遗漏任何东西，如果你指的是这篇维基文章

在修改后的版本中，values数组应该与w数组相同。计算m[n,W]后，只需检查它是否等于W。

编辑:如果您有无限数量的项目，那么您正在处理的是无界背包问题。这是一个不同的问题，同一篇文章给出了解决这个问题的动态规划实现。