0-1 Knapsack Problem

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In 0-1 Knapsack, items cannot be broken: we either take the complete item (1) or leave it (0).

Examples

Example

Values: [60, 100, 120]
Weights: [10, 20, 30]
Capacity (W): 50
Output: 220 (by taking items with weights 20 and 30, total value = 100 + 120 = 220).

Mathematical Substructure

Let dp[i][j] represent the maximum value obtained using the first i items with a knapsack capacity of j.

If weight of the i-th item is greater than capacity j (wt[i-1] > j): We cannot include this item. dp[i][j] = dp[i-1][j]
If weight of the i-th item is less than or equal to capacity j (wt[i-1] <= j): We take the maximum of excluding the item or including it: dp[i][j] = max(dp[i-1][j], val[i-1] + dp[i-1][j - wt[i-1]])

1. Recursive Solution (Naive)

function knapsackRecursive(W, wt, val, n) {
    // Base Case
    if (n === 0 || W === 0) return 0;
 
    // If weight of the nth item is more than Knapsack capacity W,
    // then this item cannot be included in the optimal solution
    if (wt[n - 1] > W) {
        return knapsackRecursive(W, wt, val, n - 1);
    }
 
    // Return the maximum of two cases:
    // (1) nth item included
    // (2) not included
    else {
        return Math.max(
            val[n - 1] + knapsackRecursive(W - wt[n - 1], wt, val, n - 1),
            knapsackRecursive(W, wt, val, n - 1)
        );
    }
}

2. Memoization Solution (Top-Down DP)

function knapsackMemoization(W, wt, val, n) {
    // Create 2D array initialized with -1
    const memo = Array.from({ length: n + 1 }, () => new Array(W + 1).fill(-1));
 
    function helper(i, w) {
        if (i === 0 || w === 0) return 0;
 
        if (memo[i][w] !== -1) return memo[i][w];
 
        if (wt[i - 1] > w) {
            memo[i][w] = helper(i - 1, w);
        } else {
            memo[i][w] = Math.max(
                val[i - 1] + helper(i - 1, w - wt[i - 1]),
                helper(i - 1, w)
            );
        }
 
        return memo[i][w];
    }
 
    return helper(n, W);
}

3. Tabulation Solution (Bottom-Up DP)

function knapsackTabulation(W, wt, val, n) {
    const dp = Array.from({ length: n + 1 }, () => new Array(W + 1).fill(0));
 
    // Build table dp[][] in bottom-up manner
    for (let i = 1; i <= n; i++) {
        for (let w = 1; w <= W; w++) {
            if (wt[i - 1] <= w) {
                dp[i][w] = Math.max(
                    val[i - 1] + dp[i - 1][w - wt[i - 1]],
                    dp[i - 1][w]
                );
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
 
    return dp[n][W];
}

4. Space Optimized Tabulation (1D DP Array)

Since the current state dp[i][w] only depends on states from the previous row dp[i-1], we can optimize space to O(W) by filling the array from right to left (to avoid overwriting values from the previous iteration that are still needed).

function knapsackSpaceOptimized(W, wt, val, n) {
    // dp[w] will store the maximum value for capacity w
    const dp = new Array(W + 1).fill(0);
 
    for (let i = 0; i < n; i++) {
        // Traverse capacity from right to left
        for (let w = W; w >= wt[i]; w--) {
            dp[w] = Math.max(dp[w], val[i] + dp[w - wt[i]]);
        }
    }
 
    return dp[W];
}
 
// Driver code
const val = [60, 100, 120];
const wt = [10, 20, 30];
const W = 50;
const n = val.length;
 
console.log("Maximum knapsack value:", knapsackSpaceOptimized(W, wt, val, n));
// Output: Maximum knapsack value: 220

Complexity Analysis

Time Complexity: O(N * W)
- Where N is the number of items and W is the capacity of the knapsack.
Space Complexity:
- O(N * W) for standard 2D Tabulation/Memoization.
- O(W) for the Space-Optimized 1D array approach.

Collect Max Coins Min Coins to Make Change