背包递归算法：帮助调试

Question

下面的背包递归定义有什么问题？我同意它写得有点古怪（更好的版本会拆分 vals 和权重，并在递归调用上携带索引），但我仍然想知道为什么这个版本不起作用。我开始了一个小时，但无济于事。

# Knapsack 
def k(items, w)
  if w == 0 || items.size < 1
    return 0
  end

  current_item = items.shift

  if current_item[1] > w
    return k(items, w)
  end

  right = current_item[0] + k(items, w - current_item[1]) 
  left  = k(items, w) 

  return [right, left].max
end

运行:

puts k([[5,10],[3,11],[7,25],[1,7]], 40)

给我 9，虽然 12 是更好的解决方案。

Answer 1

问题是调用 #shift 正在修改 same 数组，删除一个项目。

要调试此尝试打印 items 每次调用 k

一种解决方案是替换：

current_item = items.shift

和

current_item, *remaining_items = items

然后更新所有递归调用以使用 remaining_items。

举个例子可以更清楚地说明变异导致错误结果的原因，请考虑第一个调用：

物品 [5,10] 将适合背包，因此我们评估 right。每个递归调用都会改变 items 并删除一个条目。当您进入堆栈计算任何 left 时，items 数组为空。

背包递归算法：帮助调试

Knapsack recursive algorithm: help debug

ruby

knapsack-problem