self doubt

Question

Can we solve fractional knapsack using dynamic programming?

Comments

Yes , optimisation problems , than can be solved by greedy is solvable by dynamic

---

@prashant jha 1

But we won't have any advantage  over the greedy method,right?

Because the recursive soln of fractional knapsack  doesnot have any repetative sub-problems.

 

---

Check your question @DIYA BASU.

Can we solve fractional knapsack using dynamic programming

 

The question here is can we? Yes we can .

Should we ? No , because of the linear nature of the fractional knapsack(after sorting) greedy solution giving a complexity of $\Theta(nlog(n))$.

---

 

@prashant  jha 1 

Can we solve fractional knapsack using dynamic programming?

Understood your answer

Now my query is ->Dynamic programming has these 3 properties:

1>Optimal Substructure.

2>Overlapping subproblem

3>And recursive solution.

Knapsack problem (solved recursively) doesnot have over lapping subproblems is that the reason that dynamic programming would not be of any advantage?

Answer 1

Yes.... Dynamic method tries out all the possibility  and choose the best out of it....

Moreover , Greedy approach is kind of a subset to the dynamic method....

So any Greedy problem can be solved using Dynamic method...