我该如何解决这个“经典”背包递归算法？ [英] How do I solve the 'classic' knapsack algorithm recursively?
问题描述
这是我的任务。
背包问题是计算机科学的一个经典之作。在其最简单 形成它涉及试图适应不同重量的物品进入一个 背包使得背包结束与一个指定的总重量。 不需要以适合所有项目。例如，假设你想 你的背包来衡量整整20磅，你有五个项目， 为11重量，8,7，6和5磅。对于小数目的项目， 人类是pretty的善于通过观察解决这个问题。那么你 也许可以弄清楚，只有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.
当你不拿的项目，您删除，如果从你列出，但你不降低的能力。
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（因为有没拿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不采取，主叫[8 7 6 5]用容量20的
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中的实际方法可以适合于code极少数行。
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屋！
