How to Solve the 0/1 Knapsack Problem

Introduction

Consider a set of items with a weight w and profit p associated with each one of them. If we have a knapsack of capacity W, we want to fill it with the maximum set of items that give us maximum profit. A fundamental constraint for this problem is that we can include an item or not, we cannot include fractions of it. This problem and its solution problem is the 0/1 Knapsack Problem. The 0/1 part highlights the fact that we can only include integral items.

Problem Example for 0/1 Knapsack Problem

We can consider the set of items as a bi-dimensional array, and in Java, we can write it for instance as an array literal like { {w1, p1}, {w2, p2}, …}. Consider the following input for the problem:

• N = 3 items with the following values in terms of profit and weight:
  • { {1, 5}, {2, 15}, {3, 6} }
• W = 10 capacity

We cannot include the {2, 15} item, because it exceeds the maximum weight. We cannot include both {1, 5} and {3, 6}, because the sum of their weights is greater than W. We can conclude that we can obtain the maximum profit by including {3, 6} alone.

Simple Solution for 0/1 Knapsack Problem

The most immediate solution that comes to mind is to consider all the possible sub-sets and choose the sub-set with the maximum profit. Performing such tasks recursively, in evaluating each single item we have to compare these two cases, to see which gives the maximum profit:

• The current subset plus the current item if its weight is lower or equal to W (otherwise we continue with the next step of the recursion)
• The current subset without the current item

The steps described above are shown in the following code snippet:

class KnapSack01UnitTest {

    @Test
    public void knapSack01Test() throws Exception {
        int items[][] = { { 1, 5 }, { 2, 15 }, { 3, 6 } };
        int W = 10;
        int N = items.length;
        System.out.println(knapSackEvaluation(W, items, N));
    }

    private int knapSackEvaluation(int W, int items[][], int N) {

        if (N == 0 || W == 0) {
            return 0;
        }

        if (items[N - 1][1] > W) {
            return knapSackEvaluation(W, items, N - 1);
        } else {
            return maxInteger(items[N - 1][0] + knapSackEvaluation(W - items[N - 1][1], items, N - 1), knapSackEvaluation(W, items, N - 1));
        }
    }

    private int maxInteger(int a, int b) { 
        return (a > b) ? a : b; 
    }

}

Performance Considerations for the Above 0/1 Knapsack Problem Algorithm

The time complexity of the above algorithm is O(2^N).

Conclusion

In this article, we have seen a trivial way to solve the 0/1 Knapsack Problem. The example code is available on GitHub.