# 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).

```java
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.