GeeksforGeeks Medium

0/1 Knapsack

Given item weights and values and a knapsack capacity, maximise the total value carried. Each item may be taken at most once.

dpknapsack

Open on GeeksforGeeks ↗

02

Intuition

💡

Greedy by value-to-weight ratio is the natural first instinct and it is wrong here, because capacity must be packed as a whole rather than filled proportionally — a slightly worse ratio can fit the remaining space exactly. Instead ask one binary question per item: take it or skip it. Skipping leaves the same capacity with fewer items; taking spends its weight and leaves a strictly smaller capacity. Both branches are smaller subproblems, so a table over (items considered, capacity) solves each exactly once.

03

Approach

1

Two-dimensional state

dp[i][c] = best value using only the first i items within capacity c. Row 0 is all zeros — no items, no value.

2

Take or skip

If the item fits, dp[i][c] = max(skip, take) where skip = dp[i-1][c] and take = value[i] + dp[i-1][c - weight[i]]. If it does not fit, only skip is available.

3

Why the previous row

Both branches read row i-1, never row i. That is exactly what enforces 'at most once' — an item can never be consulted after it has been taken.

04

Solution & live demo

python

▶1class Solution:
▶2    def knapsack(self, wt, val, cap):
▶3        n = len(wt)
▶4        dp = [[0] * (cap + 1) for _ in range(n + 1)]
▶5        for i in range(1, n + 1):
▶6            for c in range(cap + 1):
▶7                skip = dp[i - 1][c]
▶8                if wt[i - 1] <= c:
▶9                    take = val[i - 1] + dp[i - 1][c - wt[i - 1]]
▶10                    dp[i][c] = max(skip, take)
▶11                else:
▶12                    dp[i][c] = skip
▶13        return dp[n][cap]

05

Edge cases

capacity = 0

Column 0 stays 0 — nothing fits, so no value is achievable.

Item heavier than the whole knapsack

weight > c in every column, so the value is inherited unchanged from the row above.

All items fit together

Every take branch wins and the answer is the sum of all values.

06

Complexity

Time

O(n · capacity)

Space

O(n · capacity)

Pseudo-polynomial: linear in the capacity's value, exponential in the bits used to write it. Rolling to one row gives O(capacity) space.