UGC NET CSE | September 2013 | Part 3 | Question: 42

Question

Given 0-1 knapsack problem and fractional knapsack problem and the following statements:

$S_1$: 0-1 knapsack is efficiently solved using Greedy algorithm.

$S_2$: Fractional knapsack is efficiently solved using Dynamic programming.

Which of the following is true?

• A. $S_1$ is correct and $S_2$ is not correct
• B. Both $S_1$ and $S_2$ are correct
• C. Both $S_1$ and $S_2$ are not correct
• D. $S_1$ is not correct and $S_2$ is correct

Comments

Fractional Knapsack ------>  both Greedy and DP

0/1 Knapsack----------->Only DP (Greedy fails)

Answer 1

0-1 knapsack solved by using Dynamic programming and  Fractional knapsack is solved by using greedy algorithm.

so Both S1 and S2 statement are wrong.

Answer 2

FRACTIONAL- It can be solved easily by GREEDY method so also by Dynamic

0/1- It can not be done by greedy , here optimal substructrure is required so DYNAMIC method is used

Only S2 is correct