这是我的任务
背包问题是计算机科学的经典之作。在最简单的形式中，它涉及尝试将不同重量的物品装入背包中，以便背包最终具有指定的总重量。您不需要容纳所有项目。例如，假设您希望背包的重量正好为 20 磅，并且您有五件物品，重量分别为 11、8、7、6 和 5 磅。对于少量的物品，人类非常善于通过检查来解决这个问题。因此，您可能会发现，只有 8、7 和 5 个项目组合加起来就是 20。
我真的不知道从哪里开始写这个算法。我理解应用于阶乘和三角形数时的递归。然而，我现在迷路了。
你试过了什么？
考虑到你所说的问题（它指定我们必须使用递归），这个想法很简单：对于你可以采取的每个项目，看看是否最好采取它。所以只有两种可能的路径：
当您拿走该项目时，将其从列表中删除，并将容量减小该项目的重量。
如果不获取项目，请从列表中删除 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: 8
Result: 20
我确实故意向容量为20的[8 7 6 5]显示呼叫，结果为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 人，呼叫 [6 5]，容量为 5 （12 - 7）
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
}
}
}
我确实将数组复制到一个新数组中，这效率较低（但无论如何，如果您寻求性能，递归不是这里要走的路），但更“实用”。
我必须为我的家庭作业做这件事，所以我测试了上述所有代码（除了Python代码），但是它们都不适用于每个角落的情况。
这是我的代码，它适用于每个角落的情况。
static int[] values = new int[] {894, 260, 392, 281, 27};
static int[] weights = new int[] {8, 6, 4, 0, 21};
static int W = 30;
private static int knapsack(int i, int W) {
if (i < 0) {
return 0;
}
if (weights[i] > W) {
return knapsack(i-1, W);
} else {
return Math.max(knapsack(i-1, W), knapsack(i-1, W - weights[i]) + values[i]);
}
}
public static void main(String[] args) {
System.out.println(knapsack(values.length - 1, W));}
它没有经过优化，递归会杀死你，但你可以使用简单的记忆来解决这个问题。为什么我的代码简短、正确且易于理解？我刚刚检查了0-1背包问题的数学定义 http://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming
