What does "0/1" mean?

It means you cannot divide an item. You either pick it entirely (1) or discard it (0).

State transition for Knapsack?

dp[i][w] = max(include_item, exclude_item). Include = item_val + dp[i-1][w-item_wt]. Exclude = dp[i-1][w].

The decision version is NP-Complete, but with DP, we can solve it in O(N*W) [Pseudo-polynomial time].

0/1 Knapsack

The 0/1 Knapsack problem asks which items to take, each with a weight and a value and each taken at most once, so that the total weight stays within a given limit and the total value is as large as possible.

READY

Initialize DP table. Rows: Items (0-4), Cols: Capacity (0-5)

Checking Item A (w:2, v:3) at Capacity 0

Capacity

Items (kg/$)

A 2/3 · B 3/4 · C 4/5 · D 5/6

Intuition

You are a thief with a knapsack that can hold a maximum weight W. You have a list of items, each with a weight and a value. For each item, you have to decide: take it or leave it? You cannot break an item (hence "0/1"). The goal is to maximize the total value without bursting the knapsack.

Concept

Dynamic Programming Approach:

We define dp[i][w] as the maximum value achievable using a subset of the first i items with a remaining capacity of w.

Recurrence Relation:

Don't include item i: Value is same as without it: dp[i-1][w].
Include item i (if weight[i] <= w): Value is current item's value + max value with remaining capacity: value[i] + dp[i-1][w - weight[i]].

We take the maximum of these two choices.

How it Works

Tabulation Algorithm:

Initialize a table dp of size (n+1) × (W+1) with 0s.
Iterate through items i from 1 to n.
Iterate through capacity w from 0 to W.
For each cell, apply the recurrence relation to maximize value.
The final answer is stored in dp[n][W].

Step-by-Step Breakdown

Visualizing the table:

Rows: Represent the items available so far.
Columns: Represent the current capacity limit.
Cell Value: Best value achievable for that subproblem.
Result: Bottom-right cell contains the global maximum.

When to Use

Applications:

Resource allocation with budget constraints.
Cargo loading problems.
Selection problems (e.g., cutting stock).

When NOT to Use

Fractional Items: If you can take parts of an item, use the Greedy approach (Fractional Knapsack).
Huge Capacity: If W is extremely large (10⁹), the O(nW) space/time is too slow (pseudo-polynomial).

How to Identify

"Maximize value", "Weight limit", "Pick items", "Cannot break items".

Sample Problems

Partition Equal Subset Sum

Can you split array into two equal sums? (Knapsack variant)

Target Sum

Assign +/- signs to reach target.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description

Unique Paths

Subset Sum