Question

Which of the following statement about 0/1 knapsack and fractional knapsack problem is correct?

(a) In 0/1 knapsack problem items are divisible and in fractional knapsack items are indivisible

(b) Both are the same

(c) 0/1 knapsack is solved using a greedy algorithm and fractional knapsack is solved using dynamic programming

(d) In 0/1 knapsack problem items are indivisible and in fractional knapsack items are divisible

The question was asked by my school teacher while I was bunking the class.

The query is from Greedy Algorithms in portion Greedy Algorithms of Data Structures & Algorithms II

Answer 1

Correct answer is (d) In 0/1 knapsack problem items are indivisible and in fractional knapsack items are divisible

The explanation is: In fractional knapsack problem we can partially include an item into the knapsack whereas in 0/1 knapsack we have to either include or exclude the item wholly.