Visualizers

0/1 Knapsack Visualizer

Solve the 0/1 Knapsack problem step-by-step using a 2D matrix.

native Client-side

Knapsack Capacity (1-10)

Items (wt:val comma-separated)

Speed

Ready to compute.

Execution Log

Max Value: -

Selected Items: -

Current Action:

Idle

Legend:

Uncomputed

Active Lookups

Calculated Max Value

Backtrack Path

0/1 Knapsack Algorithm

The 0/1 Knapsack problem is a classic combinatorial optimization problem. Given weights and values of $n$ items, put them in a knapsack of capacity $W$ to get the maximum total value. "0/1" means items are indivisible (you either take an item or leave it).

Dynamic Programming Formula

We maintain a 2D table `dp[i][w]` which stores the max value using a subset of first $i$ items with capacity $w$:

If weight of item $i > w$: `dp[i][w] = dp[i-1][w]`
Else: `dp[i][w] = max(dp[i-1][w], dp[i-1][w - wt[i-1]] + val[i-1])`

Implementation

function knapsack(W, weights, values) {
  const n = weights.length;
  const dp = Array.from({ length: n + 1 }, () => Array(W + 1).fill(0));
  
  for (let i = 1; i <= n; i++) {
    const wt = weights[i - 1];
    const val = values[i - 1];
    for (let w = 1; w <= W; w++) {
      if (wt > w) {
        dp[i][w] = dp[i - 1][w];
      } else {
        dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - wt] + val);
      }
    }
  }
  return dp[n][W];
}

def knapsack(W, weights, values):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        wt = weights[i - 1]
        val = values[i - 1]
        for w in range(1, W + 1):
            if wt > w:
                dp[i][w] = dp[i - 1][w]
            else:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - wt] + val)
    return dp[n][W]

public class Knapsack {
    public static int knapsack(int W, int[] weights, int[] values) {
        int n = weights.length;
        int[][] dp = new int[n + 1][W + 1];

        for (int i = 1; i <= n; i++) {
            int wt = weights[i - 1];
            int val = values[i - 1];
            for (int w = 1; w <= W; w++) {
                if (wt > w) {
                    dp[i][w] = dp[i - 1][w];
                } else {
                    dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - wt] + val);
                }
            }
        }
        return dp[n][W];
    }
}

#include <vector>
#include <algorithm>

int knapsack(int W, const std::vector<int>& weights, const std::vector<int>& values) {
    int n = weights.size();
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(W + 1, 0));

    for (int i = 1; i <= n; ++i) {
        int wt = weights[i - 1];
        int val = values[i - 1];
        for (int w = 1; w <= W; ++w) {
            if (wt > w) {
                dp[i][w] = dp[i - 1][w];
            } else {
                dp[i][w] = std::max(dp[i - 1][w], dp[i - 1][w - wt] + val);
            }
        }
    }
    return dp[n][W];
}

Related Tools

Big-O Visualizer

Interactive growth-curve chart for common complexity classes.

Data Structure Visualizer

Animated operations on linked lists, trees, stacks and hash tables.

Algorithm Visualizer

Step-through animations for sorting and pathfinding algorithms.