0-1 Knapsack

Problem

Given a backpack which can carry a weight of $W$ and $n$ snacks, each of weight $w_i$ and happiness value $h_i$, select the best possible combination of snacks to put in your backpack. Output the maximum happiness

Solution

Classic DP problem. Try it yourself first (by thinking about the subproblems).

import java.util.Scanner;

public class Knapsack {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        System.out.println("Enter capacity of bag: ");
        int w = s.nextInt();
        System.out.println("Enter number of items: ");
        int n = s.nextInt();
        System.out.println("Enter weights of all items (space-separated): ");
        int[] weights = new int[n + 1]; // weight[i] == weight of item i (1-indexed)
        int[] happiness = new int[n + 1]; // happiness[i] = happiness of item i (1-indexed)
        int temp = n;
        weights[0] = 0; // dummy item weight to make it 1-indexed
        happiness[0] = 0; // dummy item happiness to make it 1-indexed
        while (temp-- > 0) {
            weights[n - temp] = s.nextInt();
        }
        temp = n;
        System.out.println("Enter happiness of items (space-separated): ");
        while (temp-- > 0) {
            happiness[n - temp] = s.nextInt();
        }
        s.close();
        int[][] dp = new int[w + 1][n + 1];
        // dp[i][j] stores the maximum possible happiness when you have a bag of
        // capacity i and you're allowed to take the first j items
        // then, dp[i][j] = max(dp[i-1][j], dp[i][j -1], happiness[i] +
        // dp[i-weight[i]][j-1])
        // dp[i - 1][j]: take the same stuff you took when you had capacity i - 1 and
        // allowed j items
        // dp[i][j - 1]: take the same stuff you took when you had a capacity of i and
        // allowed j items
        // if you can take the ith item, try taking it and see how much from the
        // remaining capacity, how much happiness you get

        // notice we added an extra 0th row to serve as the base case of the problem:
        // when the capacity is 0, all happiness = 0 and when 0 items are allowed, max
        // happiness = 0. This forms a "border" of the dp table filled with 0's
        // this makes it easy while filling the dp table since "remaining capacity" can
        // be 0 and this disallows ArrayOutOfBoundsException
        for (int j = 0; j <= n; j++) {
            dp[0][j] = 0;
        }
        for (int j = 0; j <= w; j++) {
            dp[j][0] = 0;
        }

        // now we fill the table in increasing order of capacity, adding one element at
        // a time for each row
        for (int i = 1; i <= w; i++) {
            for (int j = 1; j <= n; j++) {
                if (weights[j] <= i) { // if there is a chance we can include item j (even if we have to remove
                                       // everything else) then try including it (and then from the remaining capacity,
                                       // take the best of the j - 1 items)
                    dp[i][j] = Math.max(Math.max(dp[i][j - 1], dp[i - 1][j]), happiness[j] + dp[i - weights[j]][j - 1]);
                    // need to do 2 Math.max because annoying Java does not allow more than 2 integers
                    // wow

                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]); // you can't include j anyway so this is the best
                                                                     // you can do
                }

            }
        }
        // our answer will be dp[w][n] (obviously)
        for (int i = 0; i <= w; i++) {
            for (int j = 0; j <= n; j++) {
                System.out.print(" " + dp[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("Maximum happiness: " + dp[w][n]);

    }
}

Time Complexity Analysis

The time complexity of this 0-1 knapsack solution is $O(nW)$ , where n is the number of items and w is the capacity of the bag. This is because the algorithm uses dynamic programming to fill up a 2D table (dp) of size (n + 1) x (w + 1), and each cell requires constant time to compute. The nested loops iterate over all items and capacities, leading to the $O(nW)$ complexity.

This illustrates a common technique to find the time complexity of any DP algorithm:

time taken per subproblem (excluding recursive calls, if any) $\times$ the number of subproblems

The space complexity is also $O(nW)$ due to the size of the dp table.