@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))$.
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?
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...
64.3k questions
77.9k answers
244k comments
80.0k users