Crack the Backend

Problem Statement

Given n items, each with a weight weights[i] and a value values[i], and a knapsack of capacity W, return the maximum total value you can obtain. Each item can be used at most once (0/1: either take the whole item or not).

We cannot exceed capacity W. All weights and values are non-negative.
Classic 0/1 knapsack: dp[i][w] = max value using the first i items with capacity w.

Key Observations

Define dp[i][w] = maximum value we can get using the first i items and capacity w. For item i-1, we either skip it (dp[i-1][w]) or take it if w >= weights[i-1] (values[i-1] + dp[i-1][w - weights[i-1]]). So dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w - weights[i-1]]) when w >= weights[i-1].
Base: dp[0][w] = 0 for all w. We can optimize space to one row dp[w] by iterating w from W down to weights[i] so we do not overwrite values we still need for the current item.

Approach

High-level: dp[w] = max value we can get with capacity w (using items processed so far). For each item, for w from W down to weights[i], dp[w] = max(dp[w], values[i] + dp[w - weights[i]]).

Steps:

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

Implementation

Java

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

    for (int i = 0; i < weights.length; i++) {
        for (int w = W; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);
        }
    }

    return dp[W];
}

Test Cases

Example 1

Input

W=4, weights=[1,2,3], values=[10,15,40]

Expected

50

Explanation

Take items 1 and 3: value 10+40=50.

Complexity Analysis

Time: O(n*W).
Space: O(W).

Follow-ups

Unbounded knapsack (each item unlimited); print chosen items.