CoreSource checked

0/1 Knapsack Dynamic Programming

Solves 0/1 knapsack by tabulating the best value for each item prefix and capacity.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Optimization
Difficulty: Intermediate
Family: Dynamic Programming
Tier: Core
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 1
Relationships: 6
Code example: Ready
Visualization: Ready

Overview

0/1 knapsack dynamic programming considers each item once and stores the best achievable value at each capacity. Each table entry chooses between skipping the item and taking it if capacity allows.

Core Concepts

knapsack optimizationdynamic programmingresidual graphoptimization

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(n log n)

Worst

O(n^2)

Space

O(n)

When to Use

Use when each item can be chosen at most once and capacities are small enough for a pseudo-polynomial table.
Use when exact optimal value matters more than a greedy approximation.

When Not to Use

Avoid when capacity values are huge and a value-scaling approximation is acceptable.
Avoid when fractional items are allowed; fractional knapsack has a simpler greedy solution.

What It Does

0/1 Knapsack Dynamic Programming uses filling a value table over items and capacity for knapsack optimization
Organizes the work around knapsack optimization and dynamic programming.

Use Cases

Production and research workloads requiring dynamic programming via Each table entry chooses between skipping the item and taking it if capacity allows.
Dynamic Programming pipelines where O(n log n) time and O(n) space fit system constraints.
Engineering comparisons against Knapsack FPTAS and Meet-in-the-Middle Knapsack when tuning dynamic programming.

Inputs

Objective, constraints, and candidate variables
Problem-specific costs or feasibility rules

Outputs

Best known feasible solution
Optimality or approximation result when available

Key Formulas (1)

Knapsack recurrence

dp_[i]_[w] = max(dp_[i−1]_[w], value_i + dp_[i−1]_{[w − weight_i]})

dp[i][w] = max(dp[i-1][w], value_i + dp[i-1][w - weight_i])

Chooses whether to include item i when it fits in the remaining capacity.

Pseudocode

1.Initialize dp[0..capacity] = 0
2.For each item with weight w and value v
3.For capacity c from capacity down to w
4.Set dp[c] = max(dp[c], dp[c - w] + v)
5.Return dp[capacity]

Canonical Example

Input: items (w=2,v=3), (w=3,v=4), (w=4,v=5), capacity 5
Output: best value 7 using the first two items
Explanation: The table compares taking and skipping each item; weights 2 and 3 fit together exactly.

Implementation Notes

Use descending capacity updates for a one-dimensional 0/1 table.
Keep weights and capacities as nonnegative integers.
Test capacity 0, overweight items, and tied optimal choices.

Common Pitfalls

Updating a one-dimensional table in the wrong direction can reuse an item more than once.
The running time depends on numeric capacity, not only item count.
Item reconstruction needs parent choices or a second pass through the table.