0 votes 0 votes Can we solve fractional knapsack using dynamic programming? Algorithms knapsack-problem dynamic-programming + – DIYA BASU asked Feb 14, 2019 • retagged Jun 17, 2022 by makhdoom ghaya DIYA BASU 507 views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply prashant jha 1 commented Feb 14, 2019 reply Follow Share Yes , optimisation problems , than can be solved by greedy is solvable by dynamic 1 votes 1 votes DIYA BASU commented Feb 14, 2019 reply Follow Share @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. 0 votes 0 votes prashant jha 1 commented Feb 14, 2019 reply Follow Share 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))$. 0 votes 0 votes DIYA BASU commented Feb 15, 2019 reply Follow Share @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? 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes 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... pradeepchaudhary answered Feb 14, 2019 pradeepchaudhary comment Share Follow See all 0 reply Please log in or register to add a comment.