Dynamic Programming • Core Concept

0/1 Knapsack

Given N items with weights and values, find the maximum value you can fit into a knapsack of capacity W. You can either pick an item (1) or not pick it (0). No duplicates allowed!

Try Interactive Simulator

Overview

This is the definitive DP problem. At each item, you make a choice: take it, or leave it. If you take it, you lose capacity `wt[i]` but gain `val[i]`.

The DP State

Using a 1D array, `dp[w]` stores the maximum value achievable with a knapsack capacity of exactly `w`.

The Transition

When considering item `i` at capacity `w`, the best choice is `max(dp[w] (leave it), dp[w - wt[i]] + val[i] (take it))`.

The Backward Loop

Because we use a 1D array and can only use each item ONCE, the capacity loop MUST run backwards from `W` down to `wt[i]`. If it ran forwards, we might use the same item multiple times!

Item 0Wt:2Val:3

Item 1Wt:3Val:4

Item 2Wt:4Val:5

DP Array (Iterating Right-to-Left)

0

1

0

2

0

3

0

4

0

5

0

Code Tracker

:::

1let dp = new Array(W + 1).fill(0);

2// Outer loop MUST be items

3for (let i = 0; i < wt.length; i++) {

4 // Inner loop MUST iterate capacity BACKWARDS

5 for (let w = W; w >= wt[i]; w--) {

6 dp[w] = Math.max(dp[w], dp[w - wt[i]] + val[i]);

7 }

8}

9return dp[W];

Zero One Knapsack

Zero One Knapsack

0/1 Knapsack

Overview

The DP State

The Transition

The Backward Loop

0/1 Knapsack

Overview

The DP State

The Transition

The Backward Loop