Visit the knapsack exercise on Exercism to read the full instructions and download the exercise files.
Dig Deeper
Recursive
Recursive
import java.util.List;
class Knapsack {
int maximumValue(int maxWeight, List<Item> items) {
if (items.isEmpty()) {
return 0;
}
List<Item> remainingItems = items.subList(1, items.size());
int valueWithout = maximumValue(maxWeight, remainingItems);
Item item = items.get(0);
if (item.weight > maxWeight) {
return valueWithout;
}
int valueWith = maximumValue(maxWeight - item.weight, remainingItems) + item.value;
return Math.max(valueWithout, valueWith);
}
}
The approach uses recursion to find the maximum value with and without each item.
Each iteration works on the first item in the list (items.get(0)).
If the list is empty, the maximum value must be 0.
Otherwise, a recursive call is made to work out the maximum value without the first item (maximumValue(maxWeight, remainingItems)).
If the there is not enough capacity to add the current item, the maximum value is the same as the maximum value without the first item.
Otherwise, another recursive call is made to calculate the maximum value with the first item.
Since the item is included, the recursive call is done with the item’s weight subtracted from the maximum weight (maxWeight - item.weight) and its value (item.value) is added.
The maximum value is greater of these two values.
Dynamic Programming
Dynamic Programming
import java.util.List;
class Knapsack {
int maximumValue(int maxWeight, List<Item> items) {
int [][]maxValues = new int[maxWeight + 1][items.size() + 1];
for (int nItems = 0; nItems <= items.size(); nItems++) {
maxValues[0][nItems] = 0;
}
for (int itemIndex = 0; itemIndex < items.size(); itemIndex++) {
Item item = items.get(itemIndex);
for (int capacity = 0; capacity <= maxWeight; capacity++) {
if (capacity < item.weight) {
maxValues[capacity][itemIndex + 1] = maxValues[capacity][itemIndex];
} else {
int valueWith = maxValues[capacity - item.weight][itemIndex] + item.value;
int valueWithout = maxValues[capacity][itemIndex];
maxValues[capacity][itemIndex + 1] = Math.max(valueWith, valueWithout);
}
}
}
return maxValues[maxWeight][items.size()];
}
}
This approach works by building a table of maximum total values.
The table is represented by the 2D array maxValues.
The table’s axes are the capacity (starting from 0 and going up to the maxWeight) and the number of items (starting from 0 and going up to length of the items list).
The number of items always count from the first item.
1 is added to the maxWeight and the number of items to allow space for 0 weight and 0 items.
The first for loop fills table for when there are no items available.
In this case, the maximum value must be 0 because there are no items.
The next for loops fills the rest of the table.
The outer for loop iterates over each item.
The inner loop fills calculates and stores the maximum value for the item and capacity.
When storing, 1 is added to the itemIndex on the left hand side because the first item in the maxValues array represents no items.
If the knapsack doesn’t have enough capacity for the item, then maximum value is same as the maximum value without the item.
The maximum value without the item is obtained simply by looking up the value for the previous item and capacity in the table (i.e maxValues[capacity][itemIndex]).
Otherwise, the maximum value is the greater of the value with and without the item.
The maximum value with (valueWith) the item is obtained by, first, looking up the maximum value without the item and enough capacity for the item (i.e capacity - item.weight).
The item’s value (item.value) is then added to get the maximum value for the get the maximum value with the item.
After the table is completely filled, the maximum value is obtained from the table.
Source: Exercism java/knapsack