0/1 Knapsack Explained: Packing Weights [1,2,3] up to Capacity 5

Imagine you are packing a cargo pod with a strict weight limit of $W=5$ kilograms. You have three discrete items to choose from. Item 1 weighs $1\text{ kg}$ and is worth 6. Item 2 weighs $2\text{ kg}$ and is worth 10. Item 3 weighs $3\text{ kg}$ and is worth 12. You cannot split items into fractions, and you cannot take duplicates of the same item. Your goal is to maximize the total value without exceeding your weight limit of $5\text{ kg}$.

If you rely on a naive greedy approach—such as picking the item with the highest value-to-weight ratio first—you might immediately grab Item 1 ($6/1=6$), then Item 2 ($10/2=5$), leaving you with a total weight of $3\text{ kg}$ and a value of 16. You have $2\text{ kg}$ of spare capacity, but Item 3 weighs $3\text{ kg}$, so it won't fit. Alternatively, if you pick the single most valuable item first, you might grab Item 3 (12), leaving $2\text{ kg}$ capacity, which lets you take Item 1 (6) for a total value of 18.

Yet, the optimal combination for this setup yields a total value of 22 by packing Item 2 and Item 3 together. This combinatorial explosion of choices explains why simple sorting fails us and why we need a systematic way to explore weight constraints without testing every single permutation by hand.

When we look at our locked working example with items $(w_1=1,v_1=6)$, $(w_2=2,v_2=10)$, and $(w_3=3,v_3=12)$ under a capacity $W=5$, every single item presents a fundamental binary question: do we include it or exclude it? Unlike continuous optimization where we might take a fraction of an item, the 0/1 restriction forces an all-or-nothing choice. This turns our packing problem into a search through a tree of subsets, where each node represents a running total of weight and value.

To model this systematically, we define our subproblem not by whether we finish the whole bag at once, but by examining smaller sub-capacities from 0 up to 5. Let $DP[c]$ represent the maximum value we can achieve given an exact capacity limit $c$. As we consider each item one by one, our available capacity acts as a tight boundary. If we look at item 3 ($w_3=3,v_3=12$), we cannot even place it into a sub-capacity of $c=2$. But at $c=5$, we have two competing futures: either we skip item 3 and keep whatever best value we built with a capacity of 5, or we include item 3, gain its 12 value, and look back at what best value we could have achieved with the remaining capacity of $5-3=2$.

This recursive relationship forces us to respect the exact order of states so we never accidentally count an item twice. If we loop forward through capacities, a single item's value might propagate multiple times into the same calculation, turning our 0/1 knapsack into an unbounded knapsack. By building our model around backwards iteration from $W$ down to $w_i$, we guarantee that each item is evaluated against the clean state of the knapsack before that item was considered.

As we evaluate this transition across all three items for our capacity limit of 5, we transition from simple guesswork to a structured table of maximum possible values for every intermediate weight.

Now that we have established our binary choice framework, let us execute the algorithm manually on our locked example: items with weights $\text{weights}=[1,2,3]$, values $\text{values}=[6,10,12]$, and capacity $W=5$. We initialize a 1D dynamic programming array of size 6 (capacities 0 through 5), all set to 0:

dp = [0, 0, 0, 0, 0, 0]

Step 1: Processing Item 1 (Weight 1, Value 6)

We iterate backward from capacity 5 down to 1. For each capacity c, we test whether including Item 1 improves our maximum value:
- $c=5$: $\max (0,\text{dp}[4]+6)=6$
- $c=4$: $\max (0,\text{dp}[3]+6)=6$
- $c=3$: $\max (0,\text{dp}[2]+6)=6$
- $c=2$: $\max (0,\text{dp}[1]+6)=6$
- $c=1$: $\max (0,\text{dp}[0]+6)=6$

Our array updates to [0, 6, 6, 6, 6, 6].

Step 2: Processing Item 2 (Weight 2, Value 10)

We iterate backward from capacity 5 down to 2:
- $c=5$: $\max (6,\text{dp}[3]+10)=\max (6,6+10)=16$
- $c=4$: $\max (6,\text{dp}[2]+10)=\max (6,6+10)=16$
- $c=3$: $\max (6,\text{dp}[1]+10)=\max (6,6+10)=16$
- $c=2$: $\max (6,\text{dp}[0]+10)=\max (6,0+10)=10$

Our array updates to [0, 6, 10, 16, 16, 16].

Step 3: Processing Item 3 (Weight 3, Value 12)

We iterate backward from capacity 5 down to 3:
- $c=5$: $\max (16,\text{dp}[2]+12)=\max (16,10+12)=22$
- $c=4$: $\max (16,\text{dp}[1]+12)=\max (16,6+12)=18$
- $c=3$: $\max (16,\text{dp}[0]+12)=\max (16,0+12)=16$

Our final DP array is [0, 6, 10, 16, 18, 22]. Inspecting index 5 reveals our expected maximum value of 22, corresponding to Item 2 and Item 3.

def knapsack_trace():
    weights = [1, 2, 3]
    values = [6, 10, 12]
    W = 5
    dp = [0] * (W + 1)
    # What is the exact state of 'dp' after processing Item 3?
    return dp

Now that you have traced the 1D DP table for our base items [1, 2, 3] with values [6, 10, 12] up to capacity $W=5$, let us test your mechanics with a slight mutation. Imagine we introduce a fourth item: weight 4 with value 18. In the classic 0/1 knapsack setup, your inner capacity loop must iterate backwards from $W$ down to the item's weight to prevent multiple inclusions of the same item.

Consider the moment we process this new fourth item $(w=4,v=18)$ against our existing table state. Without writing out the entire code execution, apply the recurrence relation $\text{dp}[c]=\max (\text{dp}[c],\text{dp}[c-w_i]+v_i)$ for capacity $c=5$. Predict how the value at $\text{dp}[5]$ updates and explain what combination of items yields this new maximum value.

Now that you have traced weights $\{1,2,3\}$ and values $\{6,10,12\}$ up to capacity $W=5$, you can recognize this exact capacity-budget recurrence in other combinatorial domains. The 0/1 knapsack pattern is not just about physical items and backpacks; it models any finite-resource allocation where choices are binary (include or exclude) and the objective is to maximize value without exceeding a hard limit. Consider a project funding scenario where you must select a subset of initiatives to fund without exceeding your capital limit. Instead of weights and values, you have costs and expected revenue. By adapting our 1D DP table formulation, you can solve these parallel problems without rewriting the core engine.

To test this transfer, consider a modified variant of our working example. Suppose your capacity remains $W=5$, but your items have weights $\{2,3,4\}$ and values $\{3,4,5\}$, and you must choose a subset that does not exceed capacity while maximizing total value. Using the same backward inner loop logic you practiced in the previous phases, what is the maximum attainable value, and which items are included?

Try this: Given items with weights [2, 3, 4] and values [3, 4, 5], and a capacity W = 5: