algorithm - 无界背包伪代码

Question

我需要为我的作业修改 wiki 的背包伪代码，以便检查您是否可以在背包中达到精确的重量 W。项目的数量是无限的，你的价值并不重要。我正在考虑在 j>-W[j] 下添加一个 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

如果我没有遗漏任何内容，如果您指的是此 wiki 文章

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

编辑：如果您有无限数量的物品，那么您正在处理Unbounded Knapsack Problem。这是一个不同的问题，同一篇文章给出了解决它的动态编程实现。