java - 递归背包返回错误答案

Question

据我所知，以下代码应该返回 16，但由于某种原因，它返回 10。有谁知道我的错误可能是什么？基本上这是 Java 中的背包问题，我已经在纸上运行了整个代码，它似乎返回了正确的答案给我，但我无法弄清楚为什么当它正确运行时，它会返回 10。

任何帮助将不胜感激。谢谢!

import java.util.Stack;

public class knapsackProblem
{

  public static int optimalValue(Stack<item> items, int totalWeight)
  {
    if (items.isEmpty())
      return 0;

    int value = items.peek().value;
    int weight = items.peek().weight;

    items.pop();

    if (totalWeight<weight)
      return optimalValue(items, totalWeight);

    return Math.max(optimalValue(items,totalWeight), value + optimalValue(items, totalWeight-weight));
  }

  public static void main(String args[])
  {
    int knapsackWeight = 15;
    Stack<item> items = new Stack<item>();

    items.push(new item(7,10));
    items.push(new item(3,6));

    System.out.println(optimalValue(items, knapsackWeight));

  }
}

class item
{
  public int weight;
  public int value;

  public item(int aWeight, int aValue)
  {
    weight = aWeight;
    value = aValue;
  }
}

Answer 1

您的Stack正在通过调用进行修改。所以一行像

return Math.max(optimalValue(items,totalWeight), value + optimalValue(items, totalWeight-weight));

每次调用都会有两个不同的项目副本。不是你想要的。

不要使用Stack，而是尝试改变一些东西以使用ArrayList。然后将您正在评估的项目的索引传递给 optimalValue 方法。这应该可以帮助您正确完成这些项目。