0/1 Knapsack

Medium20–25 min

Topics

Dynamic ProgrammingArray

Companies

AmazonMicrosoftAdobe

Given a set of items, each with a weight and a value, and a bag that can hold at most a given total weight, choose a subset of items — each usable at most once — that maximizes the total value packed into the bag without exceeding its weight capacity. Every item faces one decision: leave it out of the bag, or pack it in if there's room. Leaving it out means the best achievable value at the current capacity is whatever could already be made using the remaining items; packing it in means banking its value and continuing with less capacity to work with for the rest. Since it's never clear in advance which items are worth their weight, both choices are tried wherever an item fits, and the larger of the two resulting totals wins. Because each item is considered exactly once, tracking the best value reachable at every possible capacity — building it up one item at a time — finds the answer directly.

Test Case 1:

Input:weights = [2, 3, 4, 5], values = [3, 4, 5, 6], capacity = 5

Output:7

Explanation:Taking items 0 and 1 (weights 2+3=5, values 3+4=7) fills the bag exactly and beats every other combination.

Test Case 2:

Input:weights = [1, 4, 3], values = [15, 40, 30], capacity = 4

Output:45

Explanation:Taking items 0 and 2 (weights 1+3=4, values 15+30=45) beats taking item 1 alone (weight 4, value 40).

Test Case 3:

Input:weights = [5], values = [10], capacity = 4

Output:0

Explanation:The only item weighs more than the capacity, so nothing can be taken.

Constraints

◆1 ≤ weights.length = values.length ≤ 20
◆1 ≤ weights[i], values[i] ≤ 100
◆0 ≤ capacity ≤ 1000

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

Every item is either left out of the bag or placed into it, and an item can only be placed in if its weight doesn't exceed whatever capacity is still left. Leaving an item out keeps the remaining capacity unchanged for the rest of the items to work with; taking it adds its value to the total and uses up that much capacity for the rest. Since it's never obvious in advance which items are worth taking, both choices are tried at every item that fits, and the larger of the two resulting totals is kept. Running out of items or capacity ends a path with whatever value has been collected so far.

TimeO(2^n)

SpaceO(n)

Java

Try it out

class Solution {
    private int[] weights;
    private int[] values;

    public int knapsack01(int[] weights, int[] values, int capacity) {
        this.weights = weights;
        this.values = values;
        return solve(0, capacity);
    }

    private int solve(int i, int capacity) {
        if (i == weights.length || capacity == 0) return 0;
        if (weights[i] > capacity) return solve(i + 1, capacity);
        int skip = solve(i + 1, capacity);
        int take = values[i] + solve(i + 1, capacity - weights[i]);
        return Math.max(skip, take);
    }
}

Optimal — Bottom-Up 1D DP

Optimal

Track, for every capacity from 0 up to the bag's full capacity, the best total value achievable using the items considered so far. Every item can either be skipped (the best value at that capacity stays whatever it already was) or taken (its own value plus the best value achievable at the capacity left over after paying its weight) — whichever is larger becomes the new best at that capacity. Sweeping each item's inner update from the full capacity down to that item's own weight guarantees every item is only ever counted once. After every item has been swept through, the entry at the full capacity holds the answer.

TimeO(n × capacity)

SpaceO(capacity)