0/1 Knapsack

DSA · Dynamic Programming

Theory

In the 0/1 knapsack problem each item has a weight and a value, and you must choose items (each at most once) to maximise total value without exceeding a weight capacity. The DP state dp[w] is the best value achievable with capacity w. For each item, iterate capacity from high to low and set dp[w] = max(dp[w], dp[w - weight] + value). It runs in O(n × W) time.

Why we use it

Knapsack is the template for many resource-allocation problems with limited budgets.

When to use it

Use it for budget allocation, choosing projects within a time limit, subset sum, partition equal subset sum and target-sum problems.

How it works

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

Syntax

dp = [0] * (W + 1)
for weight, value in items:
    for w in range(W, weight - 1, -1):
        dp[w] = max(dp[w], dp[w - weight] + value)

Time: O(n·W)   Space: O(W)

Example

items = [("Laptop", 3, 60000), ("Camera", 2, 35000), ("Headphones", 1, 12000), ("Tablet", 2, 30000)]
capacity = 5

dp = [0] * (capacity + 1)
choice = [[] for _ in range(capacity + 1)]
for name, weight, value in items:
    for w in range(capacity, weight - 1, -1):
        if dp[w - weight] + value > dp[w]:
            dp[w] = dp[w - weight] + value
            choice[w] = choice[w - weight] + [name]

print("Best value:", dp[capacity])
print("Pack:", choice[capacity])

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic