Q.1 What type of problem is the Knapsack problem?
Greedy
Dynamic Programming
Divide and Conquer
Backtracking
Explanation - The Knapsack problem is a classic optimization problem solved efficiently using dynamic programming.
Correct answer is: Dynamic Programming
Q.2 In the 0/1 Knapsack problem, each item can be:
Taken multiple times
Taken only once
Divided into fractions
Ignored completely
Explanation - In 0/1 Knapsack, each item is either included or excluded; it cannot be broken down or repeated.
Correct answer is: Taken only once
Q.3 Which algorithmic technique is generally used to solve the Knapsack problem?
Greedy Algorithm
Dynamic Programming
Backtracking
Branch and Bound
Explanation - Knapsack is solved using DP by breaking it into subproblems and solving recursively with memoization or tabulation.
Correct answer is: Dynamic Programming
Q.4 What is the time complexity of the standard dynamic programming solution for 0/1 Knapsack?
O(n)
O(nW)
O(W)
O(log n)
Explanation - Here n is the number of items and W is the knapsack capacity; DP uses a table of size n × W.
Correct answer is: O(nW)
Q.5 What does 'W' represent in the Knapsack problem?
Number of items
Maximum weight capacity
Profit value
Number of subproblems
Explanation - W denotes the maximum capacity of the knapsack that can be filled.
Correct answer is: Maximum weight capacity
Q.6 What is the base case in the recursive 0/1 Knapsack solution?
When weight is 0
When number of items is 0
Both of the above
None
Explanation - If either the weight capacity is 0 or there are no items, the maximum profit is 0.
Correct answer is: Both of the above
Q.7 Which version of the Knapsack allows taking fractions of items?
0/1 Knapsack
Fractional Knapsack
Multi-dimensional Knapsack
Subset Sum
Explanation - In fractional knapsack, items can be broken into parts, and a greedy algorithm works optimally.
Correct answer is: Fractional Knapsack
Q.8 Why can't greedy algorithms solve 0/1 Knapsack optimally?
Because items are divisible
Because items are indivisible
Because weight is ignored
Because profit is ignored
Explanation - Greedy works for fractional knapsack, but in 0/1 knapsack, indivisible items may make greedy fail.
Correct answer is: Because items are indivisible
Q.9 Which of the following is NOT a variant of the Knapsack problem?
0/1 Knapsack
Fractional Knapsack
Multi-dimensional Knapsack
Prim’s Knapsack
Explanation - Prim's is a minimum spanning tree algorithm, not related to knapsack.
Correct answer is: Prim’s Knapsack
Q.10 What is the space complexity of the standard DP solution for 0/1 Knapsack?
O(nW)
O(n)
O(W)
O(1)
Explanation - The DP table has dimensions n × W, leading to O(nW) space usage.
Correct answer is: O(nW)
Q.11 How can the space complexity of 0/1 Knapsack be optimized?
Using Greedy
Using 1D array
Using Backtracking
Ignoring weights
Explanation - We can optimize space to O(W) using a rolling 1D DP array.
Correct answer is: Using 1D array
Q.12 In Knapsack DP, what does dp[i][w] represent?
Max weight at i
Max profit using first i items with weight limit w
Number of subsets
Remaining capacity
Explanation - DP state dp[i][w] stores the best value achievable with first i items under weight w.
Correct answer is: Max profit using first i items with weight limit w
Q.13 Knapsack problem is considered as:
NP-complete
NP-hard
Polynomial time solvable
Greedy solvable
Explanation - The decision version of Knapsack is NP-complete.
Correct answer is: NP-complete
Q.14 Which is a real-life application of the Knapsack problem?
Resource allocation
Job scheduling
Sorting data
Graph coloring
Explanation - Knapsack models resource allocation problems where capacity constraints exist.
Correct answer is: Resource allocation
Q.15 What approach is used in solving fractional knapsack?
Dynamic Programming
Greedy Algorithm
Backtracking
Divide and Conquer
Explanation - Fractional Knapsack can be solved optimally using a greedy approach by profit/weight ratio.
Correct answer is: Greedy Algorithm
Q.16 If there are n items and capacity W, how many subproblems exist in DP Knapsack?
n × W
n
W
2^n
Explanation - The DP table requires computing results for n items across W capacities.
Correct answer is: n × W
Q.17 Which is harder: 0/1 Knapsack or Fractional Knapsack?
0/1 Knapsack
Fractional Knapsack
Both are same
Depends on n
Explanation - Fractional Knapsack is solvable in O(n log n), while 0/1 requires O(nW) DP.
Correct answer is: 0/1 Knapsack
Q.18 What happens if item weight exceeds knapsack capacity?
Item is included partially
Item is excluded
Knapsack breaks
Profit increases
Explanation - An item cannot be included if its weight is greater than the remaining capacity.
Correct answer is: Item is excluded
Q.19 Which of these is similar to Knapsack?
Subset sum
Binary search
Dijkstra
Heap sort
Explanation - Subset sum is a special case of knapsack where values equal weights.
Correct answer is: Subset sum
Q.20 In DP Knapsack, when we skip an item, the value is taken from:
dp[i-1][w]
dp[i][w]
dp[i][w-weight]
dp[w-1][i]
Explanation - When an item is not included, the solution is same as without that item.
Correct answer is: dp[i-1][w]
Q.21 Which is the recurrence relation for 0/1 Knapsack?
dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w-weight[i]])
dp[i][w] = dp[i][w-1] + value[i]
dp[i][w] = dp[i-1][w-1]
dp[i][w] = min(...)
Explanation - Either include the item or skip it; take maximum profit.
Correct answer is: dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w-weight[i]])
Q.22 Which approach is most memory-efficient for knapsack?
2D DP
Recursive memoization
1D DP array
Greedy
Explanation - Using 1D DP reduces space to O(W) while maintaining correctness.
Correct answer is: 1D DP array
Q.23 What is the complexity of fractional knapsack?
O(n log n)
O(nW)
O(n^2)
O(log n)
Explanation - Sorting items by profit/weight ratio dominates fractional knapsack complexity.
Correct answer is: O(n log n)
Q.24 Which of these is used for solving large Knapsack instances approximately?
Exact DP
Greedy heuristics
Binary search
DFS
Explanation - For large W, exact DP is slow, so heuristics or approximations are used.
Correct answer is: Greedy heuristics
Q.25 Knapsack DP is an example of:
Overlapping subproblems and optimal substructure
Divide and Conquer only
Greedy property only
NP-hard only
Explanation - Knapsack satisfies both key DP properties.
Correct answer is: Overlapping subproblems and optimal substructure