Amazon Interview Question Consultants
Country: United States
Interview Type: Phone Interview
I think we can use greedy approach for 0-1 knapsack as after sorting by value of items, you should keep moving to i+1 item if i th does not fit in knapsack.
@Raj: that would not result in an optimal solution. Try to give an argument for why the greedy approach would be correct, and you will probably come to realize why it doesn't work.
Greedy algorithm produce optimized solution in each step, but it cannot ensure global optimized solution. Where as Dynamic Programming always produce global optimized solution.
I've also answered this in the other post. Basically the solution depends on the problem. If the problem is the 0-1 Knapsack problem, where items are not divisible; you either take an item or not, then you can ONLY use DP. However, fractional Knapsack (where items are divisible) problem can only be solved BOTH with the Greedy Algorithm and DP.
if you use greedy approach for 0-1 knapsack problem you will not get the optimal solution.
In this case greedy will give an approximate answer and why we are going for DP is yet another story.Here we will get subpriblems which will have to solve more than one time in the reccursion, So in order to reduce this overhead of solving a problem more than one time we are going for DP
Greedy Algorithm DOES NOT work for the 0-1 Knapsack problem, where items are not divisible; you either take an item or not. However, fractional Knapsack (where items are divisible) problem can be solved with Greedy Algorithm.
- oOZz July 09, 2013DP can solve both 0-1 and Fractional Knapsack problems.