Knapsack 01 solution

Question

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));
 }
}

Answer 1

Just a few comments :

---

Your if (value == 0) and if (weight == 0) should probably be if (value <= 0) and if (weight <= 0).

---

Keep It Simple : because value and weight are final, you could probably make them public, removing the need for getters.

Also, you could make this an inner class/nested class if you don't plan to use it for anything else.

---

Purely personal but I'd rather avoid continue whenever it can be easily avoided. If your case, it's quite easy to put the whole block behind a if (item != 0 && weight != 0) (or even better : if (item > 0 && weight > 0)).

However, things could be even more straightforward : for (int item = 0; item <=items.length; item++) and for (int weight = 0; weight <= maxWeight; weight++) could start at 1 because first iteration won't do anything anyway because condition if (item == 0 || weight == 0) will be true. Then, as far as I can tell, the guard is not needed anymore.

• JavaDeveloper: simple yet meaningful :)