recategorized by
7,024 views
1 votes
1 votes

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?

  1. $S_1$ is correct and $S_2$ is not correct
  2. Both $S_1$ and $S_2$ are correct
  3. Both $S_1$ and $S_2$ are not correct
  4. $S_1$ is not correct and $S_2$ is correct
recategorized by

2 Answers

1 votes
1 votes
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.
0 votes
0 votes
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
Answer:

Related questions

0 votes
0 votes
1 answer
1
go_editor asked Jul 24, 2016
1,260 views
The number of possible paranthesizations of a sequence of n matrices isO(n)$\theta$(n Ig n)$\Omega(2^n)$None of the above
1 votes
1 votes
1 answer
2
go_editor asked Jul 24, 2016
1,169 views
The time complexity of reccurence relation T(n) = T(n/3) + T(2n/3) +O(n) isO(Ig n)O(n)O(n Ig n)O(n$^2$)
1 votes
1 votes
1 answer
3
go_editor asked Jul 22, 2016
1,661 views
$\alpha - \beta$ cutoffs are applied toDepth first searchBest first searchMinimax searchBreadth first search
0 votes
0 votes
1 answer
4
im.raj asked Jun 16, 2016
1,933 views
The time complexity of an efficient algorithm to find the longest monotonically increasing subsequence of n numbers is$\text{O(n)}$$\text{O(n Ig n)}$$\text{O(n$^2$)}$None...