ToolMight LogoToolMight
Dynamic Programming & AdvancedAdvanced LevelStudy Time: 35 mins

Knapsack Problem Algorithm

The 0/1 Knapsack Problem is a dynamic programming optimization problem that selects a subset of items with given weights and values to maximize total value without exceeding capacity W.

Loading visualizer workspace...

0/1 Knapsack DP Table Worked Trace

Sample Input:Capacity W = 5, Weights = [2, 3, 4], Values = [3, 4, 5]
Step 1

Evaluate Item 1 (Weight=2, Value=3)

For capacities w=0..1, max value is 0. For w=2..5, include item 1 for total value 3.

Row 1 DP: [0, 0, 3, 3, 3, 3]
Base choices populated for first item.
Step 2

Evaluate Item 2 (Weight=3, Value=4)

At w=5, compare excluding item 2 (val 3) vs including item 2 (val 4 + dp[1][5-3]=3 = 7). Max value is 7.

Row 2 DP: [0, 0, 3, 4, 4, 7]
Combining items 1 & 2 yields weight 5 and total value 7.
Step 3

Evaluate Item 3 (Weight=4, Value=5)

At w=5, compare excluding item 3 (val 7) vs including item 3 (val 5 + dp[2][1]=0 = 5). Max remains 7.

Final Max Knapsack Value at DP[3][5]: 7
Optimal subset selected items 1 and 2.

Real-world analogy: Packing a Hiker Backpack

0/1 Choice
Hover over items for details

You have a backpack that holds at most 15 kg. You must pick items (laptop, tent, food) to get the maximum total utility without tearing the bag.

  • 0/1 Choice= Each item must be either completely included (1) or left behind (0).

Complexity analysis

Scenario Simulator: Dataset Size (N = 500)
Presets:
N = 10N = 10,000
Complexity Curve MapKnapsack Problem: O(N × W) Memoized Time
Time (t)Size N (500)N = 500O(N²)O(N log N)O(N)O(log N)O(1)Knapsack Problem
Time Steps (N=500)

500 steps (Linear)

O(N × W) Memoized Time

Space Footprint

O(N × W) Cache Matrix

Memory growth rate as N expands.

Performance Rank
Efficient Tier

Relative efficiency rating for large N.

OperationTime ComplexitySpace Complexity
DP Grid ComputationO(N × W)O(N × W)

Code implementations

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

Real-world applications

Case 01

Resource Allocation

Optimizes cloud server memory allocations within budget caps.

Case 02

Portfolio Selection

Selects optimal financial investments under risk limits.

Interview questions

Topic Knowledge Test & Assessment

10 Questions Assessment

Knapsack Knowledge & Skill Test

Validate your conceptual understanding, operation mechanics, and core concepts of Knapsack.