In this artcile, we will learn to resolve the 0-1 Knapsack problem in Java by using a dynamic programming algorithm

Problem

  • Given a knapsack with weight capacity, and a set of items, each item with a weight and a value

  • Determine the maximum value of items to include in the given knapsack so that the total weight is less than or equal to the knapsack capacity

Example

  • Given 3 items with weights = {10, 20 , 30} and values = {60, 100, 120} respectively, knapsack weight capacity is 50

  • The maximum value of items to include in the knapsack is 220

Analysis

We have 2 options at each collecting step

  • Including the i item if not exceeding the weight limit

  • Excluding the i item if exceeding the weight limit

Dynamic Programming Approach

Fill up a cache matrix int[][] cache = new int[N+1][W+1] with

  • 0 to N items as columns

  • 0 to W weight-limit as rows

  • each matrix cell cache[i][w] is the maximum value can be attained with weight less than or equal to w using i items

public class DP_Knapsack {  
    int findMaxValueOfKnapSack(int[] values, int[] weights, int W, int N) {
        int[][] cache = new int[N+1][W+1];

        for (int i = 0; i <= N; i++) {
            for (int w = 0; w <= W; w++) {
                if (i == 0 || w == 0) {
                    cache[i][w] = 0;
                }
                else if (weights[i-1] > w) {
                    cache[i][w] = cache[i-1][w];
                } else {
                    cache[i][w] = Math.max(cache[i-1][w], cache[i-1][w-weights[i-1]] + values[i-1]);
                }
            }
        }

        return cache[N][W];
    }

    public static void main(String[] args) {
        DP_Knapsack knapsack = new DP_Knapsack();
        int[] values = {60, 100, 120};
        int[] weights = {10, 20, 30};
        int weightLimit = 50;
        int noOfItems = values.length;
        System.out.println(knapsack.findMaxValueOfKnapSack(values, weights, weightLimit, noOfItems));
    }
}

  • i is the current item

  • w is the current weight limit

  • weights[i-1] is weight of current item as int[] weights is 0 based index

  • values[i-1] is value of current item as int[] values is 0 based index

  • cache[i][w] is maximum value of current item as int[][] cache is 1 based index

  • weights[i-1] > w weight of the current item is more than the weight limit

  • cache[i][w] = cache[i-1][w] excludes the current item

  • cache[i-1][w-weights[i-1]] + values[i-1] includes the current item

References

AlgorithmDynamic Programming