用递归法求解背包问题

Question

我试图在Scala中使用递归来解决背包问题，但我的要求是显示选择哪些项目保存在背包中。可用的钱表示背包大小。

我的代码如下：

def knapsack(availableMoney: Int,wt:List[Int],value :List[Int] ,n:Int) : Int= {

  if(n == 0 || availableMoney == 0)  
    return 0
  if (wt(n - 1) > availableMoney) {     
    return knapsack(availableMoney,wt,value, n - 1)
  }
  else {
    var element1 = value(n-1) + knapsack(availableMoney- wt(n-1), wt, value, n-1)
    var element2 = knapsack(availableMoney, wt, value, n-1)

    return max(element1,element2);
  }
}

如何知道选择哪些物品放在背包里？

Answer 1

请考虑接受amit的解决方案作为答案，我只想在这里补充他的解决方案之上的附加说明。

在这个解决方案中，我还将考虑背包解决方案不是唯一的情况。

正如amit所指出的，修改代码以跟踪背包中的元素是很简单的。你的方法应该返回一个tuple，而不是背包值，其中第一个条目是背包的“最大值”，第二个条目是背包中元素列表，代表背包中项目的组合。

• 第一个if对应于递归的终止条件，背包中只有一个可能的组合——没有任何元素的背包
• 如果第二个If的条件为真，则无法选择项目n-1，因此我们返回到下一个项目
• 另一方面，如果项目n-1的重量小于availableMoney，那么我们可以在构造中选择项目n-1（这对应于element1），或者在构造中保留项目n-1。然后，返回的解决方案应该是两者中更好的一个，或者如果它们给出相同的值，则将它们合并在一起

以下是代码的修改版本，供您参考：

def knapsack(availableMoney: Int, wt: List[Int], value: List[Int], n: Int): (Int, List[List[Int]]) = {

  if (n == 0 || availableMoney == 0)
    return (0, List[List[Int]](List[Int]()))

  if (wt(n - 1) > availableMoney) {
    return knapsack(availableMoney, wt, value, n - 1)
  } else {
    val recur = knapsack(availableMoney - wt(n - 1), wt, value, n - 1)
    val element1 = (recur._1 + value(n - 1), for (e <- recur._2) yield {e :+ wt(n - 1)})
    val element2 = knapsack(availableMoney, wt, value, n - 1)

    if (element1._1 > element2._1)
      return element1
    else if (element1._1 < element2._1)
      return element2
    else
      return (element1._1, element1._2 ::: element2._2)
  }
}

Answer 2

在代码中，您已经知道是否选择了当前元素。

如果选择了element1（高于element2），则最后一个（index=n-1）元素被选择。另外，你没有。

因此，您可以添加另一个要从递归调用返回的输出参数，这将指示所选元素。

你需要修改所有的返回 也要处理它：

• 返回0将变成返回（0，[]）

此外，如果您想实现is作为动态编程，这个问题讨论了如何返回元素而不仅仅是值：

如何使用背包算法（而不仅仅是包的值）找到包中的元素？