The Problem

The 0-1 Knapsack

Knapsack starts with items that have integer weights and values. The goal is to choose a subset whose total weight fits the capacity and whose total value is as large as possible. Dynamic programming is useful because brute-force subset search grows exponentially.

highlighted = computed this step

Items and capacity

There are 4 items and capacity 7. Why: each item consumes capacity and contributes value.

W=7W=7
Items and capacityThe knapsack instance lists exact integer weights, values, and capacity.itemsweightvalue11344557capacity7

Subset search

Brute force checks 16 subsets here. Why: each item is either left out or put in, so the count grows exponentially.

24=162^{4}=16
Items and capacityThe knapsack instance lists exact integer weights, values, and capacity.itemsweightvalue11344557capacity7

Diagram note

The instance data are integers and the capacity is exact; no DP values have been filled yet. Pixel positions are rounded for layout; every number shown is exact.

integer data enter the DP table\text{integer data enter the DP table}
Items and capacityThe knapsack instance lists exact integer weights, values, and capacity.itemsweightvalue11344557capacity7