0 1 Knapsack Problem in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does the '0 1' in the 0 1 Knapsack Problem mean?

It means each item can either be taken completely (1) or not taken at all (0). No partial items are allowed.

beginner

What is the main goal of the 0 1 Knapsack Problem?

To maximize the total value of items placed in the knapsack without exceeding its weight capacity.

intermediate

In the dynamic programming solution of 0 1 Knapsack, what does the DP table represent?

Each cell dp[i][w] represents the maximum value achievable using the first i items with a weight limit w.

intermediate

Why can't we use a greedy approach for the 0 1 Knapsack Problem?

Because choosing items based on value or weight alone may not lead to the optimal solution when items can't be split.

intermediate

What is the time complexity of the classic dynamic programming solution for the 0 1 Knapsack Problem?

O(n * W), where n is the number of items and W is the maximum weight capacity of the knapsack.

In the 0 1 Knapsack Problem, what does the '1' represent?

A Taking an item completely

B Taking half of an item

C Not taking any item

D Taking multiple copies of an item

The '1' means you either take the whole item or none at all.

Which approach is commonly used to solve the 0 1 Knapsack Problem optimally?

A Divide and Conquer

B Greedy Algorithm

C Brute Force without optimization

D Dynamic Programming

Dynamic Programming efficiently finds the optimal solution by building up answers for smaller subproblems.

What does dp[i][w] represent in the DP table for 0 1 Knapsack?

A Maximum value with first i items and weight limit w

B Minimum weight to achieve value w with i items

C Number of items chosen for weight w

D Total weight of first i items

dp[i][w] stores the best value achievable using first i items within weight w.

What is the main constraint in the 0 1 Knapsack Problem?

A Total value must be less than capacity

B Items can be split into fractions

C Total weight of chosen items must not exceed knapsack capacity

D All items must be chosen

The knapsack cannot hold items exceeding its weight limit.

Why is the greedy approach not suitable for the 0 1 Knapsack Problem?

A Because greedy is too slow

B Because items cannot be split and greedy may miss optimal combinations

C Because greedy always picks all items

D Because greedy requires sorting by weight only

Greedy fails when items can't be split and the best combination isn't just the highest value or lowest weight items.

Explain how the dynamic programming table is built for the 0 1 Knapsack Problem.

Think about how you decide to take or skip each item for every weight limit.

Describe why the 0 1 Knapsack Problem cannot be solved optimally by a greedy method.

Consider an example where picking the best item first leads to a worse total value.