13.7 Knapsack

The knapsack problem occupies a special place in dynamic programming. It is one of the earliest problems many programmers encounter, yet it contains nearly every important dynamic programming concept: state design, recurrence construction, resource constraints, optimization objectives, space reduction, and problem variations.

More importantly, knapsack serves as a modeling framework. A surprising number of practical optimization problems can be transformed into knapsack variants. Budget allocation, project selection, cargo loading, portfolio construction, scheduling, resource planning, and capacity management often reduce to choosing a subset of options subject to constraints.

This section develops the classical 0/1 knapsack problem and introduces the techniques that form the foundation for more advanced variants.

Problem

Given:

(n) items
weight (w_i)
value (v_i)
knapsack capacity (W)

Select items whose total weight does not exceed (W) while maximizing total value.

Each item may be chosen at most once.

Example:

Item	Weight	Value
A	2	3
B	3	4
C	4	5
D	5	8

Capacity:

$$ W = 8 $$

Goal:

maximize value
subject to weight limit

Why Greedy Fails

A natural idea is to choose the most valuable item first.

Suppose:

Item	Weight	Value
A	10	100
B	9	99
C	1	1

Capacity:

$$ 10 $$

Choosing A yields:

$$ 100 $$

Choosing B and C yields:

$$ 100 $$

Now modify the values slightly:

Item	Weight	Value
A	10	100
B	9	99
C	1	2

Greedy chooses A:

$$ 100 $$

Optimal solution:

$$ 99 + 2 = 101 $$

Local choices do not guarantee global optimality.

This immediately suggests dynamic programming.

State Design

The critical observation is that every decision depends on two facts:

which items remain available
how much capacity remains

A natural state is:

$$ dp[i][c] $$

Meaning:

maximum value obtainable
using first i items
with capacity c

This state captures all information required for future decisions.

Understanding the Subproblem

Consider:

$$ dp[5][20] $$

This asks:

Using only the first five items,
what is the largest value obtainable
without exceeding capacity 20?

Notice how this mirrors the original problem.

Dynamic programming succeeds because large problems can be decomposed into smaller versions of the same question.

Deriving the Recurrence

Focus on item (i).

Two possibilities exist.

Case 1: Skip the Item

The solution remains:

$$ dp[i-1][c] $$

Case 2: Take the Item

If:

$$ weight_i \le c $$

then:

$$ value_i + dp[i-1][c-weight_i] $$

becomes possible.

The recurrence is:

$$ dp[i][c] = \max \left( dp[i-1][c], ; dp[i-1][c-weight_i]+value_i \right) $$

This simple recurrence is the heart of the knapsack algorithm.

Table Construction

Consider:

Item	Weight	Value
A	2	3
B	3	4
C	4	5

Capacity:

$$ 5 $$

Create a table:

Items	2	3	4	5
0 items	0	0	0	0
A	3	3	3	3
A,B	3	4	4	7
A,B,C	3	4	5	7

The answer appears in:

$$ dp[n][W] $$

which equals:

$$ 7 $$

The optimal solution selects A and B.

Implementation

func Knapsack(
    weights []int,
    values []int,
    capacity int,
) int {

    n := len(weights)

    dp := make([][]int, n+1)

    for i := range dp {
        dp[i] = make([]int, capacity+1)
    }

    for i := 1; i <= n; i++ {

        weight := weights[i-1]
        value := values[i-1]

        for c := 0; c <= capacity; c++ {

            dp[i][c] = dp[i-1][c]

            if weight <= c {

                candidate :=
                    dp[i-1][c-weight] + value

                if candidate > dp[i][c] {
                    dp[i][c] = candidate
                }
            }
        }
    }

    return dp[n][capacity]
}

This implementation follows the recurrence directly.

Complexity Analysis

State count:

$$ (n+1)(W+1) $$

Each state performs constant work.

Time complexity:

$$ O(nW) $$

Memory complexity:

$$ O(nW) $$

Notice that complexity depends on capacity rather than the number of bits needed to represent capacity.

This distinction becomes important when analyzing large instances.

Reconstructing the Selected Items

Often the value alone is insufficient.

We may also want to know which items were chosen.

Starting from:

$$ dp[n][W] $$

compare:

$$ dp[i][c] $$

with:

$$ dp[i-1][c] $$

If they differ:

item i was selected

Move to:

$$ (i-1,; c-weight_i) $$

Otherwise:

item i was skipped

Move to:

$$ (i-1,; c) $$

This process reconstructs an optimal solution.

Space Optimization

Observe the recurrence carefully:

$$ dp[i][c] $$

depends only on:

$$ dp[i-1][*] $$

The entire previous table is unnecessary.

Store only one row:

dp := make([]int, capacity+1)

Process capacities in reverse order:

for _, item := range items {

    for c := capacity; c >= item.Weight; c-- {

        dp[c] = max(
            dp[c],
            dp[c-item.Weight]+item.Value,
        )
    }
}

Memory decreases from:

$$ O(nW) $$

to:

$$ O(W) $$

while preserving correctness.

Why Reverse Iteration Matters

Suppose capacity increases from left to right.

Then:

current row values

can accidentally influence later computations.

The same item may be selected multiple times.

Reverse iteration guarantees:

every item contributes at most once

This property is essential for 0/1 knapsack.

Common Mistakes

Forward Capacity Iteration

for c := weight; c <= capacity; c++

This produces a different algorithm.

Items can be reused multiple times.

The result becomes unbounded knapsack rather than 0/1 knapsack.

Incorrect State Meaning

Some implementations mix:

remaining capacity

and:

used capacity

Choose one interpretation and maintain it consistently.

Missing Base Cases

The first row:

$$ dp[0][c] $$

must represent:

no items available

Therefore every entry equals zero.

Oversized Tables

When capacity is large, an (O(nW)) table may exceed available memory.

The one-dimensional optimization often becomes necessary.

Recognizing Knapsack Problems

Many problems hide the knapsack structure behind different terminology.

Typical clues include:

fixed resource budget
capacity constraint
weight or cost limit
subset selection
maximize benefit
minimize cost
choose each option at most once

Examples:

project portfolio selection
advertisement budgeting
cloud resource allocation
shipping optimization
capital investment planning
feature prioritization

Whenever you see:

choose a subset
subject to a resource constraint

knapsack should immediately come to mind.

Variants

Several important algorithms grow directly from 0/1 knapsack:

Unbounded Knapsack
Bounded Knapsack
Multiple Knapsack
Multi-Dimensional Knapsack
Subset Sum
Partition Equal Subset Sum
Target Sum
Coin Change

Many advanced dynamic programming problems are simply knapsack variations with different state interpretations.

Takeaway

The 0/1 knapsack problem demonstrates the core dynamic programming workflow: identify the information needed for future decisions, define a state around that information, enumerate all valid choices, and construct a recurrence that selects the best outcome. The resulting algorithm runs in (O(nW)) time, supports efficient solution reconstruction, and can be optimized to (O(W)) memory. More importantly, knapsack provides a reusable modeling framework for a large class of constrained optimization problems that appear throughout algorithm design.