0 - 1 Knapsack Problem

Time: O(n*W)

Space: O(n*W)

Intuition

Each item is either taken (0) or not (1). DP table dp[i][w] = max value using first i items with capacity w. Taking item i: dp[i][w] = dp[i-1][w-wi] + vi. Not taking: dp[i][w] = dp[i-1][w]. Optimise to 1D by processing weights in reverse.

Algorithm

1Initialise dp[W+1] = 0.
2For each item i: for w from W down to weights[i]: dp[w] = max(dp[w], dp[w-weights[i]] + values[i]).
3Return dp[W].

Example Walkthrough

Input: weights=[1,3,4,5], values=[1,4,5,7], W=7

1.Item 1 (w=1,v=1): dp[1..7] updated. Item 2 (w=3,v=4): dp[7]=dp[4]+4=5.
2.Item 3 (w=4,v=5): dp[7]=dp[3]+5=9. Item 4 (w=5,v=7): dp[7]=max(9,dp[2]+7)=9.

Output: 9

Common Pitfalls

•Process weights in reverse (W down to wi) to prevent reusing the same item.

0 - 1 Knapsack Problem.java

Java

// Approach: DP (top-down memoization). For each item decide to include (if weight allows) or exclude.
// State: (index, remaining capacity). Recurse with memoization.
// Time: O(n*W) Space: O(n*W)
import java.util.*;

class Solution {
    // Function to return max value that can be put in knapsack of capacity W.
    static int knapSack(int W, int wt[], int val[]) {
        int n = val.length;
        int[][] dp = new int[n][W + 1];

        for (int[] row : dp)
            Arrays.fill(row, -1);

        return topDown(0, W, wt, val, n, dp);
    }

    static int topDown(int i, int W, int[] wt, int[] val, int n, int[][] dp) {
        if (i >= n || W <= 0)
            return 0;

        if (dp[i][W] != -1)
            return dp[i][W];

        int nottake = topDown(i + 1, W, wt, val, n, dp);

        int take = 0;
        if (W - wt[i] >= 0)
            take = val[i] + topDown(i + 1, W - wt[i], wt, val, n, dp);

        return dp[i][W] = Math.max(take, nottake);
    }
}

Was this solution helpful?