Dynamic Programming: 0/1 Knapsack Quiz

What is the time complexity of the dynamic programming solution for the 0/1 Knapsack problem with n items and W capacity?

• O(n log W)

• O(nW)

• O(n²)

• O(W log n)

What is the base case in the DP approach for the 0/1 Knapsack problem?

• When capacity W = 0 or number of items n = 0

• When all items have the same weight

• When all items have the same value

• When n is even

In dynamic programming, what is the key concept used to solve the 0/1 Knapsack problem efficiently?

• Memoization

• Greedy approach

• Divide and conquer

• Recursion only

How does the dynamic programming solution for the 0/1 Knapsack problem store intermediate results?

• In a hash table

• In a 2D array (table)

• In a linked list

• It does not store intermediate results

If we use a space-optimized approach, what is the space complexity of the 0/1 Knapsack dynamic programming solution?

• O(nW)

• O(n²)

• O(W)

• O(1)

Which of the following recurrence relations correctly represents the DP solution for the 0/1 Knapsack problem?

• dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i])

• dp[i][w] = min(dp[i-1][w], dp[i-1][w-wt[i]] + val[i])

• dp[i][w] = dp[i-1][w] + dp[i][w-wt[i]]

• dp[i][w] = dp[i][w-wt[i]] - val[i]

What is the main difference between the 0/1 Knapsack and the Fractional Knapsack problem?

• 0/1 Knapsack allows breaking items into smaller parts

• Fractional Knapsack is solved using a greedy approach, while 0/1 Knapsack uses DP

• Fractional Knapsack has a higher time complexity than 0/1 Knapsack

• 0/1 Knapsack is always more efficient than Fractional Knapsack

Which data structure is typically used to implement the dynamic programming solution for the 0/1 Knapsack problem?

• Stack

• Queue

• 2D Array (Table)

• Graph

Suppose you have n items and a knapsack with capacity W. What happens if all items have weights greater than W?

• The total profit is maximized

• The knapsack remains empty

• The smallest item is always selected

• An error occurs in the algorithm

What is the purpose of using a bottom-up approach in the dynamic programming solution for the 0/1 Knapsack problem?

• To avoid recursion and stack overflow issues

• To minimize the number of function calls

• To increase the problem complexity

• To use more memory for better results