Solution to bounded knapsack 01 problem. Once again comprehensive description is difficult in this space, refer here. Looking for code review. optimizations and best practices.
final class Item {
private final int value;
private final int weight;
public Item (int value, int weight) {
if (value == 0) {
throw new IllegalArgumentException("The value " + value + " should be positive.");
}
if (weight == 0) {
throw new IllegalArgumentException("The weight " + weight + " should be positive.");
}
this.value = value;
this.weight = weight;
}
public int getValue() {
return value;
}
public int getWeight() {
return weight;
}
}
public final class Knapsack01 {
private Knapsack01() { }
/**
* Returns the maximum value, given set of items and maxweight
*
* @param items the set of items.
* @param maxWeight the max weight
* @return the max value obeying the constraints
*/
public static int getMaxValue (Item[] items, int maxWeight) {
if (maxWeight <= 0) {
throw new IllegalArgumentException("the maxweight: " + maxWeight + " should be positive");
}
int[][] knapsack = new int[items.length + 1][maxWeight + 1];
for (int item = 0; item <=items.length; item++) {
for (int weight = 0; weight <= maxWeight; weight++) {
if (item == 0 || weight == 0) {
continue;
}
int itemWeight = items[item - 1].getWeight();
if (weight >= itemWeight) {
int remainingWeight = weight - itemWeight;
// check the max value upto remainingWieght, the we might have computed before.
int valueUptoRemainingWeight = knapsack[item - 1][remainingWeight];
// how about trying currentItem + remainingItem ?
int tentativeValue = items[item - 1].getValue() + valueUptoRemainingWeight;
// compare this against previously calculated max-value
int previousMaxValue = knapsack[item - 1][weight];
knapsack[item][weight] = Math.max(tentativeValue, previousMaxValue);
} else {
knapsack[item][weight] = knapsack[item - 1][weight];
}
}
}
return knapsack[items.length][maxWeight];
}
public static void main(String[] args) {
Item i1 = new Item( 60, 10);
Item i2 = new Item(100, 20);
Item i3 = new Item(120, 30);
Item[] items = new Item[3];
items[0] = i1;
items[1] = i2;
items[2] = i3;
assertEquals(180, getMaxValue(items, 40));
assertEquals(220, getMaxValue(items, 50));
assertEquals(280, getMaxValue(items, 60));
assertEquals(280, getMaxValue(items, 60));
}
}
