Knapsack Problem

A classic optimization problem that aims to maximize the total value of items placed in a knapsack without exceeding its capacity. Commonly solved using dynamic programming.

Knapsack Problem Visualization

Items — Capacity:

Cameraw=2 v=6
Laptopw=3 v=9
Notebookw=1 v=3
Headphonesw=2 v=7
Bookw=1 v=2
SlowFast
🔊 Sound
ReadyAdd items and set capacity, then press Run.
Take (better)Skip / Can't fitPendingIn optimal solution
012345W →∅Cameraw=2 v=6Laptopw=3 v=9Notebookw=1 v=3Headphonesw=2 v=7Bookw=1 v=2

Complexity

Time Complexity: O(n * W)
Space Complexity: O(n * W)

Pseudocode

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