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

Recall & Review

beginner

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

To select items with given weights and values to maximize total value without exceeding the knapsack's weight capacity.

beginner

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

Each item can be either taken (1) or not taken (0); partial items are not allowed.

intermediate

What is the time complexity of the 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.

intermediate

What does the DP table represent in the 0 1 Knapsack Problem?

It stores the maximum value achievable using the first i items with a weight limit j.

intermediate

How do you decide whether to include an item in the knapsack during the DP solution?

Compare the value of including the item (value + best value for remaining weight) with excluding it, and choose the maximum.

What does the 'weight capacity' in the 0 1 Knapsack Problem represent?

A Total number of items available

B Maximum total weight the knapsack can hold

C Maximum value achievable

D Number of items selected

The weight capacity is the limit on the total weight the knapsack can carry.

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

A Dynamic Programming

B Greedy Algorithm

C Brute Force without optimization

D Divide and Conquer

Dynamic Programming efficiently solves the problem by storing intermediate results.

In the DP table, what does the entry dp[i][j] represent?

A Maximum value using first i items with weight limit j

B Weight of the ith item

C Number of items selected so far

D Minimum weight to achieve value j

dp[i][j] stores the best value achievable with first i items and weight limit j.

If an item's weight is more than the current weight limit j, what happens in the DP solution?

A Weight limit j is increased

B Item is included anyway

C Algorithm stops

D Item is excluded; dp[i][j] = dp[i-1][j]

If the item is too heavy, it cannot be included, so the value remains as without it.

What is the key difference between 0 1 Knapsack and Fractional Knapsack?

A 0 1 Knapsack allows partial items; Fractional does not

B Both allow partial items

C 0 1 Knapsack does not allow partial items; Fractional does

D Neither allows partial items

0 1 Knapsack requires whole items; Fractional Knapsack allows fractions of items.

Explain how dynamic programming solves the 0 1 Knapsack Problem step-by-step.

Think about building solutions from smaller subproblems.

Describe the difference between the 0 1 Knapsack Problem and the Fractional Knapsack Problem.

Focus on item selection rules and solution methods.