DSA Dynamic Programming

Knapsack Problem

You need the highest-value subset of ad creatives that fits a 10 MB payload budget. Whole files only: no fractions. The variant (0/1, fractional, unbounded) is part of the API contract.

State first: item prefix and remaining capacity for . Do not mix that with greedy or reuse.

Decision journey

Name the variant

0/1, fractional, or unbounded?

Define state

Usually (items considered, remaining capacity).

Write transitions

Skip vs take; loop direction encodes reuse.

O(nW) only if W is modest.

What actually happens

Naive idea: try all 2ⁿ subsets, or greed by for indivisible items. Subsets explode; density greed fails on classic 0/1 counterexamples.

Better idea: for 0/1, DP over capacity. Each item is considered once; time O(nW) when W is the capacity magnitude. For fractions, sort by density and fill.

The improved design still fails when W is huge (pseudo-polynomial blow-up), when you use the wrong loop direction (accidental unbounded), or when multiple dimensions break the 1D recurrence.

Invariant

After processing the first i items, dp[w] (or dp[i][w]) equals the maximum value achievable with capacity w using only those items under the chosen reuse rule.

How to choose a knapsack method

1. Divisible items? Fractional: greedy by density in O(n log n).

2. Copies allowed? Unbounded vs 0/1 changes the capacity loop.

3. Capacity magnitude? Modest W: capacity DP. Huge W: rethink (value DP, MITM, FPTAS).

Quantitative check

n = 100, W = 10⁴: about 10⁶ cell updates, fine. n = 40, W = 10⁹: 2⁴⁰ or nW both fail; meet-in-the-middle (2ⁿᐟ²) or approximation is the next move. Density greed on weights (2,3) values (3,4) with W = 4 can pick wrong for 0/1.

0/1 Knapsack DP Visualizer

🍎Applew:1 v:2

📚Bookw:3 v:4

💻Laptopw:4 v:5

🏆Goldw:5 v:7

Step 0 of -1

0kg

1kg

2kg

3kg

4kg

5kg

6kg

7kg

No Items

🍎

Applew:1 v:2

📚

Bookw:3 v:4

💻

Laptopw:4 v:5

🏆

Goldw:5 v:7

Current Cell

Exclude (Previous Row)

Include Base (Value Source)

Final Path

Three contracts that must not be mixed

0/1 Knapsack

Take each item entirely or not at all (no fractions).

•Solution: Dynamic Programming
•Time: O(n × W) pseudo-polynomial
•Example: Packing whole items
•NP-hard optimization; its threshold decision version is NP-complete

Fractional Knapsack

Can take fractions of items (like liquids or gold dust).

•Solution: Greedy Algorithm
•Time: O(n log n) - sorting
•Example: Filling with water, sand, gold
•Polynomial time (efficient!)

Unbounded Knapsack

May take any number of copies of each item.

• DP direction: capacity moves forward
• Time: O(n × W) pseudo-polynomial
• Example: reusable product types or coin-style choices
• A zero-weight positive-value item makes the optimum unbounded

🔍 Why pseudo-polynomial is not polynomial

The 0/1 Knapsack optimization problem is NP-hard; the decision question “is value at least K?” is NP-complete. However, the capacity-indexed DP solution ispseudo-polynomial - it's polynomial in the numeric value of the capacity, not its bit representation. For modest capacities, DP is practical. With huge capacities, value-DP, meet-in-the-middle, branch-and-bound, or an approximation scheme may be better depending on n and the value range.

💻 0/1 Knapsack (Dynamic Programming)

Problem Definition

Given:

• n items, each with weight w[i] and value v[i]
• Knapsack capacity W

Find:

Subset of items that maximizes total value while total weight ≤ W

Python

python

def knapsack_01(
    weights: list[int], values: list[int], capacity: int
) -> tuple[int, list[int]]:
    """Return optimal value and one deterministic set of item indices."""
    if len(weights) != len(values):
        raise ValueError("weights and values must have equal length")
    if capacity < 0 or any(weight < 0 for weight in weights):
        raise ValueError("capacity and weights must be nonnegative")

    item_count = len(weights)
    # dp[i][w]: best value from the first i items with capacity at most w.
    dp = [[0] * (capacity + 1) for _ in range(item_count + 1)]

    for i, (weight, value) in enumerate(zip(weights, values), start=1):
        for limit in range(capacity + 1):
            best = dp[i - 1][limit]  # skip item i-1
            if weight <= limit:
                candidate = dp[i - 1][limit - weight] + value
                if candidate > best:  # ties deliberately prefer skipping
                    best = candidate
            dp[i][limit] = best

    selected = []
    limit = capacity
    for i in range(item_count, 0, -1):
        if dp[i][limit] != dp[i - 1][limit]:
            selected.append(i - 1)
            limit -= weights[i - 1]
    selected.reverse()
    return dp[item_count][capacity], selected


if __name__ == "__main__":
    weights = [0, 1, 3, 4, 5]
    values = [2, -4, 4, 5, 7]
    optimum, chosen = knapsack_01(weights, values, 7)
    assert optimum == 11 and chosen == [0, 2, 3]
    print(optimum, chosen)

Java

java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Knapsack01 {
    static final class KnapsackResult {
        final long maxValue;
        final List<Integer> selectedItems;

        KnapsackResult(long maxValue, List<Integer> selectedItems) {
            this.maxValue = maxValue;
            this.selectedItems = selectedItems;
        }
    }

    public static KnapsackResult solve(int[] weights, long[] values, int capacity) {
        validate(weights, values, capacity);
        int itemCount = weights.length;
        long[][] dp = new long[itemCount + 1][capacity + 1];

        for (int i = 1; i <= itemCount; i++) {
            int weight = weights[i - 1];
            long value = values[i - 1];
            for (int limit = 0; limit <= capacity; limit++) {
                long best = dp[i - 1][limit];
                if (weight <= limit) {
                    long candidate = Math.addExact(
                            dp[i - 1][limit - weight], value);
                    if (candidate > best) best = candidate;
                }
                dp[i][limit] = best;
            }
        }

        List<Integer> selected = new ArrayList<>();
        int limit = capacity;
        for (int i = itemCount; i > 0; i--) {
            if (dp[i][limit] != dp[i - 1][limit]) {
                selected.add(i - 1);
                limit -= weights[i - 1];
            }
        }
        Collections.reverse(selected);
        return new KnapsackResult(dp[itemCount][capacity], selected);
    }

    private static void validate(int[] weights, long[] values, int capacity) {
        if (weights.length != values.length) {
            throw new IllegalArgumentException("weights and values differ");
        }
        if (capacity < 0) throw new IllegalArgumentException("negative capacity");
        for (int weight : weights) {
            if (weight < 0) throw new IllegalArgumentException("negative weight");
        }
    }

    public static void main(String[] args) {
        int[] weights = {0, 1, 3, 4, 5};
        long[] values = {2, -4, 4, 5, 7};
        KnapsackResult result = solve(weights, values, 7);
        assert result.maxValue == 11;
        assert result.selectedItems.equals(List.of(0, 2, 3));
        System.out.println(result.maxValue + " " + result.selectedItems);
    }
}

Space-Optimized 0/1 and Unbounded Versions

Python

python

def knapsack_01_optimized(
    weights: list[int], values: list[int], capacity: int
) -> int:
    if len(weights) != len(values) or capacity < 0:
        raise ValueError("invalid lengths or capacity")
    if any(weight < 0 for weight in weights):
        raise ValueError("0/1 weights must be nonnegative")

    dp = [0] * (capacity + 1)
    for weight, value in zip(weights, values):
        # Backward: dp[limit-weight] still belongs to the previous item row.
        for limit in range(capacity, weight - 1, -1):
            dp[limit] = max(dp[limit], dp[limit - weight] + value)
    return dp[capacity]


def knapsack_unbounded(
    weights: list[int], values: list[int], capacity: int
) -> int:
    if len(weights) != len(values) or capacity < 0:
        raise ValueError("invalid lengths or capacity")
    if any(weight <= 0 for weight in weights):
        raise ValueError("unbounded items require strictly positive weights")

    dp = [0] * (capacity + 1)
    for weight, value in zip(weights, values):
        # Forward: the current item may feed another copy of itself.
        for limit in range(weight, capacity + 1):
            dp[limit] = max(dp[limit], dp[limit - weight] + value)
    return dp[capacity]


if __name__ == "__main__":
    assert knapsack_01_optimized([3, 4], [4, 5], 7) == 9
    assert knapsack_unbounded([3, 4], [4, 5], 8) == 10
    assert knapsack_01_optimized([0], [7], 0) == 7

Java

java

public class KnapsackOptimized {
    public static long knapsack01(
            int[] weights, long[] values, int capacity) {
        validateLengths(weights, values, capacity);
        long[] dp = new long[capacity + 1];
        for (int i = 0; i < weights.length; i++) {
            if (weights[i] < 0) {
                throw new IllegalArgumentException("negative 0/1 weight");
            }
            for (int limit = capacity; limit >= weights[i]; limit--) {
                long candidate = Math.addExact(
                        dp[limit - weights[i]], values[i]);
                dp[limit] = Math.max(dp[limit], candidate);
            }
        }
        return dp[capacity];
    }

    public static long knapsackUnbounded(
            int[] weights, long[] values, int capacity) {
        validateLengths(weights, values, capacity);
        long[] dp = new long[capacity + 1];
        for (int i = 0; i < weights.length; i++) {
            if (weights[i] <= 0) {
                throw new IllegalArgumentException(
                        "unbounded items require positive weights");
            }
            for (int limit = weights[i]; limit <= capacity; limit++) {
                long candidate = Math.addExact(
                        dp[limit - weights[i]], values[i]);
                dp[limit] = Math.max(dp[limit], candidate);
            }
        }
        return dp[capacity];
    }

    private static void validateLengths(
            int[] weights, long[] values, int capacity) {
        if (weights.length != values.length || capacity < 0) {
            throw new IllegalArgumentException("invalid lengths or capacity");
        }
    }

    public static void main(String[] args) {
        assert knapsack01(new int[] {3, 4}, new long[] {4, 5}, 7) == 9;
        assert knapsackUnbounded(new int[] {3, 4}, new long[] {4, 5}, 8) == 10;
        assert knapsack01(new int[] {0}, new long[] {7}, 0) == 7;
        System.out.println(knapsack01(
                new int[] {3, 4}, new long[] {4, 5}, 7));
    }
}

🎯 Key Insight: DP Recurrence

The DP recurrence captures the decision at each step:

dp[i][w] = max(dp[i−1][w], dp[i−1][w−wᵢ] + vᵢ), when wᵢ ≤ w

Translation: For item i and capacity w, either:
1. Don't take item i → value is dp[i-1][w]
2. Take item i → value is dp[i-1][w - weight[i]] + value[i]
Choose whichever is larger!

State invariant, loop direction, and reconstruction

2D invariant

After row i, every dp[i][w] is optimal among subsets of the first i items whose total weight is at most w. Skip/take exhausts the two possibilities for item i, giving an induction proof.

Why backward means 0/1

Descending capacity reads the previous item layer before it is overwritten. Ascending capacity can read a state updated by the same item, intentionally changing the contract to unbounded knapsack.

Reconstruction

In the 2D table, a changed value between rows proves that item was selected; subtract its weight and continue. A 1D value table discards that history unless parent decisions or recomputation are added.

After item	capacities 0…7	Interpretation
none	0 0 0 0 0 0 0 0	empty subset
(w=3,v=4)	0 0 0 4 4 4 4 4	one copy only
(w=4,v=5)	0 0 0 4 5 5 5 9	capacity 7 combines both

💻 Fractional Knapsack (Greedy)

Python

python

from fractions import Fraction


def fractional_knapsack(
    weights: list[int], values: list[int], capacity: int
) -> tuple[Fraction, list[tuple[int, Fraction]]]:
    if len(weights) != len(values) or capacity < 0:
        raise ValueError("invalid lengths or capacity")
    if any(weight < 0 for weight in weights):
        raise ValueError("weights must be nonnegative")

    total = Fraction(0)
    taken: list[tuple[int, Fraction]] = []
    candidates = []
    for index, (weight, value) in enumerate(zip(weights, values)):
        if weight == 0:
            if value > 0:  # fraction is bounded by one, so take it fully
                total += value
                taken.append((index, Fraction(1)))
        elif value > 0:  # optional nonpositive items never improve the objective
            candidates.append(index)

    candidates.sort(
        key=lambda index: (Fraction(values[index], weights[index]), -index),
        reverse=True,
    )
    remaining = capacity
    for index in candidates:
        if remaining == 0:
            break
        fraction = min(Fraction(1), Fraction(remaining, weights[index]))
        total += values[index] * fraction
        taken.append((index, fraction))
        remaining -= int(weights[index] * fraction)
    return total, taken


if __name__ == "__main__":
    optimum, chosen = fractional_knapsack(
        [0, 10, 20, 30], [5, 60, 100, 120], 50
    )
    assert optimum == 245
    assert chosen[-1] == (3, Fraction(2, 3))
    print(float(optimum), chosen)

Java

java

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class FractionalKnapsack {
    record Fraction(BigInteger numerator, BigInteger denominator) {
        Fraction {
            if (denominator.signum() == 0) throw new ArithmeticException("zero denominator");
            if (denominator.signum() < 0) {
                numerator = numerator.negate();
                denominator = denominator.negate();
            }
            BigInteger divisor = numerator.gcd(denominator);
            numerator = numerator.divide(divisor);
            denominator = denominator.divide(divisor);
        }

        static Fraction of(long value) {
            return new Fraction(BigInteger.valueOf(value), BigInteger.ONE);
        }

        static Fraction of(long numerator, long denominator) {
            return new Fraction(BigInteger.valueOf(numerator), BigInteger.valueOf(denominator));
        }

        Fraction add(Fraction other) {
            return new Fraction(
                    numerator.multiply(other.denominator).add(other.numerator.multiply(denominator)),
                    denominator.multiply(other.denominator));
        }

        Fraction multiply(long factor) {
            return new Fraction(numerator.multiply(BigInteger.valueOf(factor)), denominator);
        }

        double doubleValue() {
            return numerator.doubleValue() / denominator.doubleValue();
        }
    }

    static final class Item {
        final int index;
        final long weight;
        final long value;

        Item(int index, long weight, long value) {
            this.index = index;
            this.weight = weight;
            this.value = value;
        }
    }

    static final class ItemTaken {
        final int index;
        final Fraction fraction;

        ItemTaken(int index, Fraction fraction) {
            this.index = index;
            this.fraction = fraction;
        }
    }

    static final class Result {
        final Fraction value;
        final List<ItemTaken> taken;

        Result(Fraction value, List<ItemTaken> taken) {
            this.value = value;
            this.taken = taken;
        }
    }

    public static Result solve(long[] weights, long[] values, long capacity) {
        if (weights.length != values.length || capacity < 0) {
            throw new IllegalArgumentException("invalid lengths or capacity");
        }
        List<Item> items = new ArrayList<>();
        List<ItemTaken> taken = new ArrayList<>();
        Fraction totalValue = Fraction.of(0);
        for (int i = 0; i < weights.length; i++) {
            if (weights[i] < 0) throw new IllegalArgumentException("negative weight");
            if (weights[i] == 0 && values[i] > 0) {
                totalValue = totalValue.add(Fraction.of(values[i]));
                taken.add(new ItemTaken(i, Fraction.of(1)));
            } else if (weights[i] > 0 && values[i] > 0) {
                items.add(new Item(i, weights[i], values[i]));
            }
        }

        // Compare a.value/a.weight without floating-point rounding or overflow.
        Comparator<Item> byDensity = (left, right) -> {
            BigInteger leftCross = BigInteger.valueOf(left.value)
                    .multiply(BigInteger.valueOf(right.weight));
            BigInteger rightCross = BigInteger.valueOf(right.value)
                    .multiply(BigInteger.valueOf(left.weight));
            int densityOrder = rightCross.compareTo(leftCross);
            return densityOrder != 0
                    ? densityOrder : Integer.compare(left.index, right.index);
        };
        items.sort(byDensity);

        long remaining = capacity;
        for (Item item : items) {
            if (remaining == 0L) break;
            if (item.weight <= remaining) {
                totalValue = totalValue.add(Fraction.of(item.value));
                remaining -= item.weight;
                taken.add(new ItemTaken(item.index, Fraction.of(1)));
            } else {
                Fraction fraction = Fraction.of(remaining, item.weight);
                totalValue = totalValue.add(fraction.multiply(item.value));
                taken.add(new ItemTaken(item.index, fraction));
                remaining = 0L;
                break;
            }
        }
        return new Result(totalValue, taken);
    }

    public static void main(String[] args) {
        Result result = solve(
                new long[] {0, 10, 20, 30},
                new long[] {5, 60, 100, 120}, 50);
        assert result.value.equals(Fraction.of(245));
        assert result.taken.get(result.taken.size() - 1).index == 3;
        assert result.taken.get(result.taken.size() - 1).fraction.equals(Fraction.of(2, 3));
        System.out.println(result.value.doubleValue());
    }
}

Why density greedy is correct only for fractions

Suppose a fractional solution uses positive weight from a lower-density item while a higher-density item is not yet full. Exchange an equal amount of weight between them: capacity is unchanged and value cannot decrease. Repeating this exchange produces the density-sorted greedy solution. With indivisible items that exchange may be illegal, which is exactly why the same greedy rule fails for 0/1 knapsack.

Zero weight

A positive-value 0/1 or fractional item is taken once; in unbounded knapsack it makes the optimum infinite.

Negative value

Because selecting nothing is allowed, an optional negative-value item is never useful.

Numeric safety

Python uses exact Fraction ratios; Java cross-multiplies with BigInteger and uses long/Math.addExact in integral DP.

Choose the state space that is actually small

Method	Cost	Choose when
Capacity DP	O(nW), O(W) values	Weights and W are nonnegative integers and W is the small dimension.
Value DP	O(nS), S = sum of positive values	Store minimum weight achieving each value when capacity is huge but S is modest.
Meet in the middle	O(2^(n/2)) time/space	n is modest but numeric weights/capacity are too large for pseudo-polynomial DP; enumerate halves and prune dominated pairs.
Subset bitset	About O(nW / word-size)	Fast reachability/subset-sum feasibility; recovering maximum arbitrary value needs more state.
FPTAS / scaling	Polynomial in n and 1/ε	A controlled approximation is acceptable and exact dimensions are both too large.
Fractional greedy	O(n log n)	Fractions are genuinely allowed; it does not approximate the 0/1 contract by itself.

Value-DP recurrence: let minWeight[v] be the minimum weight needed for exact value v. Iterate values backward for each 0/1 item and update minWeight[v + valueᵢ]. The largest v with minWeight[v] ≤ W is optimal. As with capacity DP, direction encodes whether reuse is allowed.

💡 Pro Tip: When to Use Which?

Use 0/1 Knapsack (DP) when:

• Items are indivisible (can't take fractions)
• Capacity is reasonable (DP table fits in memory)
• Need exact optimal solution

Use Fractional Knapsack (Greedy) when:

• Items are divisible (liquids, powders, etc.)
• Need fast solution (O(n log n) vs O(n×W))
• Greedy gives optimal solution for this variant!

Use Unbounded Knapsack when:

• Item types may be reused without a copy limit
• Every reusable weight is strictly positive
• Forward capacity iteration intentionally permits repeated copies

Production contract and verification

State whether capacity means “at most” or “exactly,” whether the empty solution is allowed, and whether item counts are 0/1, bounded, or unbounded.
Reject mismatched arrays, negative capacity, and negative weights. Decide zero-weight behavior before allocating a DP table.
Python integers avoid value-sum overflow. Java examples store values in long and use Math.addExact so overflow fails loudly.
Guard (n+1)×(W+1) before 2D allocation. O(nW) can be infeasible even when the asymptotic expression looks familiar.
Property-test small instances against exhaustive subset enumeration; verify capacity, value, no duplicate 0/1 indices, reconstruction value, and agreement between 2D and 1D DP.
Include empty input, zero capacity, all negative values, zero-weight items, duplicate items, ties, one item too heavy, and deliberately overflowing Java totals.

✅ Pros & ❌ Cons

✅ Advantages

✓DP gives exact optimal solution for 0/1
✓Greedy is very fast for fractional variant
✓Can be space-optimized to O(W)
✓Practical for reasonable capacities
✓Models many real-world problems

❌ Disadvantages

✗0/1 optimization is NP-hard; its decision form is NP-complete
✗DP is pseudo-polynomial (depends on W)
✗Impractical for very large capacities
✗Greedy doesn't work for 0/1 variant
✗May need approximation for huge instances

💼 Modeling patterns and limits

💰 Portfolio Optimization

A single-budget project-selection model resembles knapsack. Real portfolios add correlated risk, continuous quantities, transaction costs, and regulatory constraints, usually requiring richer optimization models.

Use knapsack only after validating the independence and single-capacity assumptions.

📦 Cargo Loading

Selecting indivisible cargo under one weight limit is 0/1 knapsack. Weight plus volume, balance, hazardous-goods rules, and routing turn it into multidimensional or mixed-integer optimization.

Multiple resource dimensions invalidate the one-dimensional recurrence.

💾 Resource Allocation

Selecting optional jobs under a fixed memory or accelerator budget can form a knapsack subproblem. Deadlines, fairness, preemption, and multiple resources require scheduling or online-allocation models.

Example: Cloud computing, server allocation

🎯 Project Selection

Independent projects with fixed cost and value fit 0/1 knapsack. Dependencies, mutual exclusion, uncertainty, and yearly budgets add graph and stochastic constraints.

Example: R&D budgeting, startup funding

Exercises

Items (w,v) = (2,3), (3,4), capacity 4. Show a greedy packing that loses to the 0/1 optimum.
Same items with unbounded copies: how do the 1D loop directions differ from 0/1, and what are the two optima?
n = 80, W = 10¹². Why is O(nW) DP not a plan? Name one exact alternative when values are small.

Primary sources

Cormen et al., CLRS: 0/1 knapsack DP; fractional knapsack greedy.
Kellerer, Pferschy, Pisinger: Knapsack Problems (variants and complexity).
Garey & Johnson: NP-completeness of the knapsack decision problem.

Takeaway

Name the variant first. 0/1 needs state-based DP; fractional needs a density exchange proof; loop direction encodes reuse.