如何递归解决“经典"背包算法? [英] How do I solve the 'classic' knapsack algorithm recursively?
问题描述
这是我的任务
背包问题是计算机科学中的经典之作.在最简单的形式它涉及尝试将不同重量的物品放入一个背包，以便背包最终具有指定的总重量.您不需要适合所有项目.例如，假设你想要你的背包正好重 20 磅，你有五件物品，重量分别为 11、8、7、6 和 5 磅.对于少量物品，人类很擅长通过检查来解决这个问题.那么你大概可以算出只有8、7、5项的组合加起来是 20.
The Knapsack Problem is a classic in computer science. In its simplest form it involves trying to fit items of different weights into a knapsack so that the knapsack ends up with a specified total weight. You don't need to fit in all the items. For example, suppose you want your knapsack to weigh exactly 20 pounds, and you have five items, with weights of 11, 8, 7, 6, and 5 pounds. For small numbers of items, humans are pretty good at solving this problem by inspection. So you can probably figure out that only the 8, 7, and 5 combination of items adds up to 20.
我真的不知道从哪里开始编写这个算法.我理解应用于阶乘和三角形数时的递归.然而我现在迷路了.
I really don't know where to begin writing this algorithm. I understand recursion when applied to factorials and triangle numbers. However I'm lost right now.
推荐答案
你尝试了什么?
考虑到您提出的问题(指定我们必须使用递归)，这个想法很简单:对于您可以接受的每个项目，看看是否接受它更好.所以只有两条可能的路径:
The idea, given the problem you stated (which specifies we must use recursion) is simple: for each item that you can take, see if it's better to take it or not. So there are only two possible path:
- 你拿走物品
- 你不接受
当您拿走物品时，您会将其从清单中删除，并根据物品的重量减少容量.
When you take the item, you remove it from your list and you decrease the capacity by the weight of the item.
当您不拿走该项目时，您将 if 从列表中删除，但不会减少容量.
When you don't take the item, you remove if from you list but you do not decrease the capacity.
有时打印递归调用的样子会有所帮助.在这种情况下，它可能如下所示:
Sometimes it helps to print what the recursive calls may look like. In this case, it could look like this:
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
我特意展示了对 [8 7 6 5] 的调用，容量为 20，结果为 20 (8 + 7 + 5).
I did on purpose show the call to [8 7 6 5] with a capacity of 20, which gives a result of 20 (8 + 7 + 5).
注意 [8 7 6 5] 被调用了两次:一次是容量为 20(因为我们没有取 11)，一次是容量为 9(因为 with 取了 11).
Note that [8 7 6 5] is called twice: once with a capacity of 20 (because we didn't take 11) and once with a capacity of 9 (because with did take 11).
解决方案的路径:
11 未取，调用容量为 20 的 [8 7 6 5]
11 not taken, calling [8 7 6 5] with a capacity of 20
8 个，调用 [7 6 5]，容量为 12 (20 - 8)
8 taken, calling [7 6 5] with a capacity of 12 (20 - 8)
取7，调用[6 5]，容量为5 (12 - 7)
7 taken, calling [6 5] with a capacity of 5 (12 - 7)
6 未取，调用容量为 5 的 [5]
6 not taken, calling [5] with a capacity of 5
5 分，我们为零.
Java 中的实际方法可以用很少的代码行.
The actual method in Java can fit in very few lines of code.
既然这显然是家庭作业，我就帮你做个骨架:
Since this is obviously homework, I'll just help you with a skeleton:
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
}
}
}
我确实将数组复制到了一个新数组，这效率较低(但无论如何，如果您寻求性能，递归不是去这里的方法)，但更实用".
I did copy the array to a new array, which is less efficient (but anyway recursion is not the way to go here if you seek performance), but more "functional".
这篇关于如何递归解决“经典"背包算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
