0/1 Knapsack

Category: Dynamic Programming

The problem

Given a set of items, each with a weight and a value, and a capacity budget, choose the subset that maximizes total value without exceeding the budget — each item taken whole or not at all (no splitting an item across the "0" and "1" of taking it or not, hence the name). Trying every subset directly is O(2^n): for even a modest 20-30 items, that's tens of millions to a billion combinations to check.

The solution

Define dp[i][w] as the best value achievable using only the first i items within capacity w. That value only ever depends on the row above it: either item i is skipped (dp[i][w] = dp[i-1][w]), or it's taken, using up weight[i] of the capacity (dp[i][w] = dp[i-1][w - weight[i]] + value[i]) — take whichever of those two is larger. Filling that table bottom-up touches each (item, capacity) cell once: O(n × capacity). Walking back through the finished table from dp[n][capacity], comparing each row to the one above to see whether including that item's value was what made the cell improve, recovers exactly which items were chosen — without re-solving anything.

flowchart LR
    subgraph "dp[i][w] depends only on the row above"
        direction TB
        A["dp[i-1][w]  (skip item i)"]
        B["dp[i-1][w - weight(i)] + value(i)  (take item i)"]
        A --> C["dp[i][w] = max(A, B)"]
        B --> C
    end

Classic example

classic/Knapsack implements both the DP table fill plus backtracking (solve, returning a KnapsackResult with the max value and which items were chosen) and a direct recursive brute force (bruteForceMaxValue) for the benchmark below to measure against. KnapsackTest covers a case with a unique optimal combination (verified against the item selection, not just the value), zero capacity, no items, a single item that fits, a single item that doesn't, brute force agreeing with the DP result on the same input, and the null/mismatched-length/negative- capacity guards.

Applied example: telecom capex project selection

applied/CapexProjectSelector selects which candidate infrastructure projects to fund out of a fixed annual capex budget, maximizing total projected value — the textbook business framing of 0/1 knapsack: a project either gets funded in full or not at all, there's no such thing as funding 60% of a fiber build-out, and the budget is the hard capacity constraint. Real project lists are small enough that the DP table's cost is trivial in practice, but the selection problem itself is exactly as combinatorially hard as any other knapsack instance — picking projects "by best ROI first" (a greedy shortcut) doesn't reliably find the optimal combination the way it happens to for this repo's Coin Change module on ordinary currency denominations. CapexProjectSelectorTest covers selecting the highest-value combination within budget, an empty candidate list, a zero budget, and the null-argument guard.

Benchmark

./gradlew :dynamic-programming:knapsack:jmh

Real run on this machine (JMH 1.37, JDK 26.0.2, 2 warmup + 3 measurement iterations, 1 fork). Item count stays small — brute force at 22 items is already checking over 4 million subsets, and anything larger would make this benchmark impractically slow:

At 22 items, brute force is ~1,968x slower than DP for the identical answer. Brute force's own growth confirms the exponential shape directly: going from 15 to 18 items (3 more) costs ~10.6x more time, and 18 to 22 (4 more) costs ~15.6x more — both close to the 2^3 = 8 and 2^4 = 16 growth exactly 2^n predicts. DP, meanwhile, grows gently across the same range — its cost tracks items × capacity, not 2^items.

When not to use it

• Items can be split fractionally (a "fractional knapsack" — take 60% of an item for 60% of its weight and value)? A greedy approach (highest value-per-weight first) is provably optimal for that variant — the combinatorial hardness this module's DP solves specifically comes from the all-or-nothing constraint.
• Capacity is enormous relative to the number of items (a huge budget, few candidates)? The DP table's O(n × capacity) cost scales with capacity directly — at that point brute force's O(2^n), bounded only by item count, can actually be cheaper.
• Only need the optimal value, never which items achieve it? Skip the backtracking step and keep just the final row of the DP table — halves the memory this implementation uses to also support item recovery.

Test coverage

100% instruction coverage, 100% branch coverage (JaCoCo). Reproduce it yourself:

./gradlew :dynamic-programming:knapsack:jacocoTestReport

Report at dynamic-programming/knapsack/build/reports/jacoco/test/html/index.html.

Further reading

• Cormen, Leiserson, Rivest & Stein — Introduction to Algorithms (CLRS), 3rd/4th ed., Chapter 15 problems include 0/1 knapsack as a direct application of the optimal-substructure argument the chapter builds.
• Kleinberg & Tardos — Algorithm Design, Chapter 6, "Dynamic Programming" — covers knapsack as a core worked example of the "subproblems indexed by a resource budget" DP pattern this module implements.

Unit tests

package com.algorithms.dynamicprogramming.knapsack.classic;

import org.junit.jupiter.api.Test;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class KnapsackTest {

    @Test
    void picksTheHighestValueCombinationWithinCapacity() {
        int[] weights = {1, 3, 4, 5};
        int[] values = {1, 4, 5, 7};

        KnapsackResult result = Knapsack.solve(weights, values, 7);

        assertThat(result.maxValue()).isEqualTo(9);
        assertThat(result.selected()).containsExactly(false, true, true, false);
    }

    @Test
    void zeroCapacityTakesNothing() {
        KnapsackResult result = Knapsack.solve(new int[] {2, 3}, new int[] {10, 20}, 0);

        assertThat(result.maxValue()).isZero();
        assertThat(result.selected()).containsExactly(false, false);
    }

    @Test
    void noItemsProducesZeroValue() {
        KnapsackResult result = Knapsack.solve(new int[0], new int[0], 10);

        assertThat(result.maxValue()).isZero();
        assertThat(result.selected()).isEmpty();
    }

    @Test
    void aSingleItemThatFitsIsTaken() {
        KnapsackResult result = Knapsack.solve(new int[] {5}, new int[] {10}, 5);

        assertThat(result.maxValue()).isEqualTo(10);
        assertThat(result.selected()).containsExactly(true);
    }

    @Test
    void aSingleItemThatDoesNotFitIsSkipped() {
        KnapsackResult result = Knapsack.solve(new int[] {10}, new int[] {10}, 5);

        assertThat(result.maxValue()).isZero();
        assertThat(result.selected()).containsExactly(false);
    }

    @Test
    void bruteForceAgreesWithTheDpSolutionOnTheSameInputs() {
        int[] weights = {1, 3, 4, 5};
        int[] values = {1, 4, 5, 7};

        int dpValue = Knapsack.solve(weights, values, 7).maxValue();
        int bruteForceValue = Knapsack.bruteForceMaxValue(weights, values, 7);

        assertThat(bruteForceValue).isEqualTo(dpValue);
    }

    @Test
    void rejectsNullWeightsOrValues() {
        assertThatThrownBy(() -> Knapsack.solve(null, new int[0], 1)).isInstanceOf(IllegalArgumentException.class);
        assertThatThrownBy(() -> Knapsack.solve(new int[0], null, 1)).isInstanceOf(IllegalArgumentException.class);
    }

    @Test
    void rejectsMismatchedArrayLengths() {
        assertThatThrownBy(() -> Knapsack.solve(new int[] {1, 2}, new int[] {1}, 5))
                .isInstanceOf(IllegalArgumentException.class);
    }

    @Test
    void rejectsANegativeCapacity() {
        assertThatThrownBy(() -> Knapsack.solve(new int[] {1}, new int[] {1}, -1))
                .isInstanceOf(IllegalArgumentException.class);
    }
}

package com.algorithms.dynamicprogramming.knapsack.applied;

import org.junit.jupiter.api.Test;

import java.util.List;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class CapexProjectSelectorTest {

    @Test
    void selectsTheHighestValueCombinationWithinBudget() {
        CapexProjectSelector selector = new CapexProjectSelector();
        List<CapexProject> candidates = List.of(
                new CapexProject("fiber-north", 3, 4),
                new CapexProject("fiber-south", 4, 5),
                new CapexProject("tower-upgrade", 1, 1),
                new CapexProject("backup-power", 5, 7)
        );

        List<CapexProject> selected = selector.selectWithinBudget(candidates, 7);

        assertThat(selected).extracting(CapexProject::name).containsExactly("fiber-north", "fiber-south");
    }

    @Test
    void emptyCandidateListSelectsNothing() {
        CapexProjectSelector selector = new CapexProjectSelector();

        List<CapexProject> selected = selector.selectWithinBudget(List.of(), 100);

        assertThat(selected).isEmpty();
    }

    @Test
    void zeroBudgetSelectsNothing() {
        CapexProjectSelector selector = new CapexProjectSelector();
        List<CapexProject> candidates = List.of(new CapexProject("fiber-north", 3, 4));

        List<CapexProject> selected = selector.selectWithinBudget(candidates, 0);

        assertThat(selected).isEmpty();
    }

    @Test
    void rejectsANullCandidateList() {
        CapexProjectSelector selector = new CapexProjectSelector();

        assertThatThrownBy(() -> selector.selectWithinBudget(null, 10)).isInstanceOf(IllegalArgumentException.class);
    }
}

View full JaCoCo coverage report →