如何递归解决“经典”背包算法？

你尝试了什么？

考虑到您陈述的问题（指定必须使用递归），这个想法很简单：对于您可以接受的每个项目，看看是否更好。因此，只有两种可能的路径：

1. 你拿这个东西
2. 你不接受

拿走物品时，将其从列表中删除，并通过物品的重量减少容量。

如果您不拿走物品，则从列表中删除if，但不会减少容量。

有时，它有助于打印递归调用的外观。在这种情况下，它可能看起来像这样：

Calling 11 8 7 6 5  with cap: 20 +Calling 8 7 6 5  with cap: 20 |  Calling 7 6 5  with cap: 20 |    Calling 6 5  with cap: 20 |      Calling 5  with cap: 20 |      Result: 5 |      Calling 5  with cap: 14 |      Result: 5 |    Result: 11 |    Calling 6 5  with cap: 13 |      Calling 5  with cap: 13 |      Result: 5 |      Calling 5  with cap: 7 |      Result: 5 |    Result: 11 |  Result: 18 |  Calling 7 6 5  with cap: 12 |    Calling 6 5  with cap: 12 |      Calling 5  with cap: 12 |      Result: 5 |      Calling 5  with cap: 6 |      Result: 5 |    Result: 11 |    Calling 6 5  with cap: 5 |      Calling 5  with cap: 5 |      Result: 5 |    Result: 5 |  Result: 12 +Result: 20  Calling 8 7 6 5  with cap: 9    Calling 7 6 5  with cap: 9      Calling 6 5  with cap: 9        Calling 5  with cap: 9        Result: 5        Calling 5  with cap: 3        Result: 0      Result: 6      Calling 6 5  with cap: 2        Calling 5  with cap: 2        Result: 0      Result: 0    Result: 7    Calling 7 6 5  with cap: 1      Calling 6 5  with cap: 1        Calling 5  with cap: 1        Result: 0      Result: 0    Result: 0  Result: 8Result: 20

我确实故意显示了对[8 7 6 5]的调用，其容量为20，结果为20（8 + 7 + 5）。

请注意，[8 7 6 5]被调用了两次：一次容量为20（因为我们没有取11），一次容量为9（因为我们取了11）。

因此，解决方案的路径：

11未取，呼叫[8 7 6 5]，容量为20

取8，呼叫[7 6 5]，容量为12（20-8）

取7，以5（12-7）的容量跟注[6 5]

6未取，以5的容量跟注[5]

摄5，我们为零。

Java中的实际方法几乎可以包含几行代码。

由于这显然是家庭作业，因此我将为您提供帮助：

private int ukp( final int[] ar, final int cap ) {    if ( ar.length == 1 ) {        return ar[0] <= cap ? ar[0] : 0;    } else {        final int[] nar = new int[ar.length-1];        System.arraycopy(ar, 1, nar, 0, nar.length);        fint int item = ar[0];        if ( item < cap ) { final int left = ...  // fill me: we're not taking the item final int took = ...  // fill me: we're taking the item return Math.max(took,left);        } else { return ... // fill me: we're not taking the item        }    }}

我确实将数组复制到了一个效率较低的新数组中（但是无论如何，如果您寻求性能，递归都不是这里的方法），而是更多的“功能性”。