使用递归的背包解决方案

Question

我正在尝试在 Scala 中使用递归来解决 Knapsack 问题，但我的要求是显示选择将哪些项目保留在 Knapsack 中。 availableMoney表示背包尺寸。

我的代码如下：

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

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

如果您选择了 element1（它高于 element2），则选择了最后一个 (index=n-1) 元素。否则，你没有。

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

并且您需要修改所有 return ... 以同时处理它：

return 0 会变成 return (0,[])
return knapsack(availableMoney,wt,value, n - 1) 保持原样。
return max(element1,element2) 将 return (element1, list1.add(n-1)) 或 (element2, list2)，取决于哪个更高，element 或 element2.

另外，如果你想实现动态规划，这个问题讨论如何 return 元素而不仅仅是值：

How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag's value]?

Answer 2

请考虑接受 amit 的解决方案作为答案，我只是想在这里补充一下他的解决方案。

在这个解决方案中，我也会考虑背包解决方案不唯一。

的情况

正如 amit 所指出的，修改代码以跟踪背包中的元素是很直接的。您的方法应该 return 一个 tuple 而不是背包值，其中第一个条目是背包的 "max value"，第二个条目是背包中的元素列表表示背包中物品的组合。

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

以下是修改后的代码供您参考：

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)
  }
}

使用递归的背包解决方案

Knapsack Solution using Recursion

algorithm

scala

knapsack-problem