#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/algorithms/knapsack

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/algorithms/knapsack

Repovive

0/1 Knapsack - Algorithm Tutorial | Repovive | Repovive

Repovive.

Back to Algorithms

0/1 Knapsack Algorithm Tutorial

mediumDP7 min read

Introduction

The $0/1$ Knapsack problem asks: given $n$ items, each with a weight and value, what's the maximum value you can carry in a bag with capacity $W$ ?

The " $0/1$ " means you either take an item completely or leave it behind. No splitting allowed. You can't take half a laptop.

Example: You have $3$ items:

Item A: weight $2$ , value $3$
Item B: weight $3$ , value $4$
Item C: weight $4$ , value $5$

With capacity $5$ , your best choice is items A + B for total value $7$ .

Real applications: budget allocation across projects, loading cargo onto trucks, selecting features under time constraints.

Intuition

For each item, you face a binary decision: take it or skip it.

If you take item $i$ :

Your remaining capacity drops by its weight
You gain its value
You move to the next item

If you skip item $i$ :

Capacity stays the same
You gain nothing from this item
You move to the next item

You want the combination that maximizes total value without exceeding capacity $W$ .

Think of it recursively. At each step, you compare: "What's better? Taking this item (if it fits) or skipping it?" The answer depends on what you can do with the remaining items and remaining capacity.

DP State & Transition

You define $dp[i][w]$ as the maximum value achievable using the first $i$ items with capacity $w$ .

Base case: $dp[0][w] = 0$ for all $w$ . With zero items, you get zero value.

Transition: For each item $i$ with weight $wt[i]$ and value $val[i]$ :

$dp[i][w] = \max(dp[i-1][w], \quad dp[i-1][w - wt[i]] + val[i])$

The first term is skipping item $i$ . The second term is taking it (only valid when $w \geq wt[i]$ ).

You build the table row by row. Each cell asks: "Given this capacity and these items available, what's the best I can do?" The answer at $dp[n][W]$ gives your final result.

Implementation

Here's the complete $2$ D dynamic programming solution:

text

function knapsack(weights, values, W):
    n = length(weights)
    dp = 2D array of size (n+1) x (W+1), initialized to 0
    
    for i from 1 to n:
        for w from 0 to W:
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1])
            else:
                dp[i][w] = dp[i-1][w]
    
    return dp[n][W]

Reconstructing the solution: Start at $dp[n][W]$ . If $dp[i][w] \neq dp[i-1][w]$ , item $i$ was taken. Move to $dp[i-1][w - weights[i-1]]$ . Otherwise, move to $dp[i-1][w]$ . Repeat until $i = 0$ .

Implement this Algorithm

Go to Problem

Related Algorithms

Edit Distance

medium2 min

Dynamic Programming (Fibonacci)

easy1 min

Longest Common Subsequence (LCS)

medium2 min

You can reduce space from $O(n \times W)$ to $O(W)$ using a $1$ D array.

The trick: iterate capacity backwards. This prevents overwriting values you still need.