1
\$\begingroup\$

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));
    }
}
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ simple yet meaningful :) \$\endgroup\$ Mar 31, 2014 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.