SimuVedaAlgorithms Lab Open in the lab

Dynamic programming / Advanced

0/1 Knapsack Visualizer

dp[i][w] is the best value using the first i items with capacity w. Either skip item i (cell above) or take it (value + the cell up and to the left).

Start the 0/1 Knapsack simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n·W)
Average timeO(n·W)
Worst timeO(n·W)
Extra spaceO(n·W)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Rows are items, columns are capacities. The "none" row is all 0.
  2. Item 1 (weight 1) does not fit in capacity 0. Copy 0 from above.
  3. Item 1, capacity 1: skip = 0, take = 0 + 1 = 1. Best is 1.
  4. Item 1, capacity 2: skip = 0, take = 0 + 1 = 1. Best is 1.
  5. Item 1, capacity 3: skip = 0, take = 0 + 1 = 1. Best is 1.
  6. Item 1, capacity 4: skip = 0, take = 0 + 1 = 1. Best is 1.
  7. Item 1, capacity 5: skip = 0, take = 0 + 1 = 1. Best is 1.
  8. Item 1, capacity 6: skip = 0, take = 0 + 1 = 1. Best is 1.
  9. Item 1, capacity 7: skip = 0, take = 0 + 1 = 1. Best is 1.
  10. Item 2 (weight 3) does not fit in capacity 0. Copy 0 from above.
  11. Item 2 (weight 3) does not fit in capacity 1. Copy 1 from above.
  12. Item 2 (weight 3) does not fit in capacity 2. Copy 1 from above.
  13. Item 2, capacity 3: skip = 1, take = 0 + 4 = 4. Best is 4.
  14. Item 2, capacity 4: skip = 1, take = 1 + 4 = 5. Best is 5.
  15. Item 2, capacity 5: skip = 1, take = 1 + 4 = 5. Best is 5.
  16. Item 2, capacity 6: skip = 1, take = 1 + 4 = 5. Best is 5.
  17. Item 2, capacity 7: skip = 1, take = 1 + 4 = 5. Best is 5.
  18. Item 3 (weight 4) does not fit in capacity 0. Copy 0 from above.
  19. Item 3 (weight 4) does not fit in capacity 1. Copy 1 from above.
  20. Item 3 (weight 4) does not fit in capacity 2. Copy 1 from above.
  21. … 10 more steps …
  22. Item 4, capacity 5: skip = 6, take = 0 + 7 = 7. Best is 7.
  23. Item 4, capacity 6: skip = 6, take = 1 + 7 = 8. Best is 8.
  24. Item 4, capacity 7: skip = 9, take = 1 + 7 = 8. Best is 9.
  25. The best value is 9. Items taken: #2, #3.

Try it with your own input →

2D DP: 0/1 knapsack in Java, Python, C++, C and JavaScript

int knapsack(int[] wt, int[] val, int W) {
  int n = wt.length;
  int[][] dp = new int[n + 1][W + 1];
  for (int i = 1; i <= n; i++) {
    for (int w = 0; w <= W; w++) {
      dp[i][w] = dp[i - 1][w];
      if (wt[i - 1] <= w)
        dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - wt[i - 1]] + val[i - 1]);
    }
  }
  return dp[n][W];
}
def knapsack(wt, val, W):
    n = len(wt)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(W + 1):
            dp[i][w] = dp[i - 1][w]
            if wt[i - 1] <= w:
                dp[i][w] = max(dp[i][w], dp[i - 1][w - wt[i - 1]] + val[i - 1])
    return dp[n][W]
int knapsack(const vector<int>& wt, const vector<int>& val, int W) {
  int n = wt.size();
  vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
  for (int i = 1; i <= n; i++) {
    for (int w = 0; w <= W; w++) {
      dp[i][w] = dp[i - 1][w];
      if (wt[i - 1] <= w)
        dp[i][w] = max(dp[i][w], dp[i - 1][w - wt[i - 1]] + val[i - 1]);
    }
  }
  return dp[n][W];
}
int knapsack(int wt[], int val[], int n, int W) {
  int dp[n + 1][W + 1];
  for (int w = 0; w <= W; w++) dp[0][w] = 0;
  for (int i = 1; i <= n; i++) {
    for (int w = 0; w <= W; w++) {
      dp[i][w] = dp[i - 1][w];
      if (wt[i - 1] <= w && dp[i - 1][w - wt[i - 1]] + val[i - 1] > dp[i][w])
        dp[i][w] = dp[i - 1][w - wt[i - 1]] + val[i - 1];
    }
  }
  return dp[n][W];
}
function knapsack(wt, val, W) {
  const n = wt.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(W + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= W; w++) {
      dp[i][w] = dp[i - 1][w];
      if (wt[i - 1] <= w)
        dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - wt[i - 1]] + val[i - 1]);
    }
  }
  return dp[n][W];
}

In an interview

0/1 Knapsack. Same pattern: LeetCode 416 Partition Equal Subset Sum and 494 Target Sum.

The last frame traces back from the bottom-right cell to find which items were taken. Interviewers often ask for that, not just the number.

More dynamic programming