What did you try?
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:
- you take the item
- you don’t take it
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
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).
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).
So the path to the solution:
11 not taken, calling [8 7 6 5] with a capacity of 20
8 taken, calling [7 6 5] with a capacity of 12 (20 – 8)
7 taken, calling [6 5] with a capacity of 5 (12 – 7)
6 not taken, calling [5] with a capacity of 5
5 taken, we’re at zero.
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”.