Knapsack Problem

Problem Statement

Given n items, each with a weight and a value, and a knapsack that can carry at most W weight, find the maximum total value you can fit in the knapsack. You can either take an item or leave it (0/1 — no splitting allowed).

Example:

• Input: weights = [1, 3, 4, 5], values = [1, 4, 5, 7], W = 7
• Output: 9 (pick items with weight 3 and 4, values 4 + 5 = 9)

Noob-Friendly Explanation

Imagine you're going on a trip and your bag can hold only 7 kg. You have 4 items on your bed — each has a weight and a "happiness value." You want to pack items that make you the happiest, but you can't exceed 7 kg. You can't cut an item in half — you either take the whole thing or leave it. This problem finds the best combination to maximize happiness.

Approach 1: Brute Force (Recursion)

Intuition

For every item, you have two choices — take it or leave it. Try all combinations and pick the one with the highest value that stays within the weight limit.

Algorithm

1. Start from the last item
2. If the item's weight is more than remaining capacity, skip it
3. Otherwise, try both taking it and leaving it, return the max

public class Solution {
    public int knapsack(int[] weights, int[] values, int W, int n) {
        // Base case: no items left or bag is full
        if (n == 0 || W == 0) return 0;

        // If current item is too heavy, skip it
        if (weights[n - 1] > W) {
            return knapsack(weights, values, W, n - 1);
        }

        // Take or leave — pick the better option
        int take = values[n - 1] + knapsack(weights, values, W - weights[n - 1], n - 1);
        int leave = knapsack(weights, values, W, n - 1);

        return Math.max(take, leave);
    }
}

Complexity Analysis

• Time Complexity: O(2^n) - Each item has 2 choices, leading to exponential combinations
• Space Complexity: O(n) - Recursion stack depth equals the number of items

Approach 2: Optimal (Bottom-Up DP)

Intuition

Build a 2D table where dp[i][w] represents the maximum value achievable using the first i items with capacity w. Fill it row by row — each row depends only on the previous row.

Algorithm

1. Create a 2D array dp[n+1][W+1] initialized to 0
2. For each item i and each capacity w:
   • If item i fits, decide whether including it gives a better result
   • dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w - weights[i-1]])
3. Answer is dp[n][W]

public class Solution {
    public int knapsack(int[] weights, int[] values, int W, int n) {
        int[][] dp = new int[n + 1][W + 1];

        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= W; w++) {
                // Don't take item i
                dp[i][w] = dp[i - 1][w];

                // Take item i if it fits
                if (weights[i - 1] <= w) {
                    dp[i][w] = Math.max(dp[i][w],
                        values[i - 1] + dp[i - 1][w - weights[i - 1]]);
                }
            }
        }

        return dp[n][W];
    }
}

Complexity Analysis

• Time Complexity: O(n * W) - We fill an n × W table, each cell in O(1)
• Space Complexity: O(n * W) - The 2D DP table