Greedy vs Dynamic

Question

Unlike greedy algorithms, dynamic programming method always provide correct/optimal solution.

Is the above statement correct?

Comments

No this is not true. Dynamic can solve every problem but can't provide optimized solution everytime.

---

Dynamic always give correct answer, but its not as optimized as greedy since in dynamic you consider every cases possible.

---

What is the difference between optimized and correct?

Correct answer implies optimized isn't? If the answer is not optimized then how can it be correct?

DP doesn't give correct solution for fractional knapsack but Greedy does, so how can the above statement be correct?

---

Optimization in terms of complexities , you can write bubble sort and merge sort for sorting elements, merge sort has better time complexity so its more optimize in terms of time if you compare it with bubble sort.
Correctness doesnot depend on optimization, you may write a bad code and still get correct answer.

---

I don't think optimized here means in terms of Analysis of Algorithms.

It refers to finding accurate answers.

---

Yes, Dynamic programming does provide correct solution always. Greedy works as "The best thing to do this moment" while dynamic programming focuses on dividing problem into subproblems and then solve subproblems. Then uses solutions to subproblems to construct solution for large problem.

Dynamic programming considers all possible solutions. Fractional knapsack can be solved using Dynamic but a greedy approach is faster.

---

@Gaurav

So can I say these two statements:

DP solves all problems "CORRECTLY( providing the correct answer)" having optimal substructure property but may not be the optimal algorithm to do so. It gives optimal time complexity solution, only for problems where apart from "optimal substructure" property there exists "overlapping subproblems" property too but not "greedy-choice" property.

On the other hand, problems exhibiting in addition to "optimal substructure" property, "greedy-choice" property but not "overlapping subproblems" property then the optimal time complexity solution is ONLY given by Greedy algo and not DP( which only provides the correct solution ).

---

Yes. Overlapping solutions is what DP takes advantage of. In any case, it runs till base condition is met. However, stored results (if there are overlapping problems) makes it faster. 

Okay. Correct vs Optimal . The question is talking about solution and has nothing to do with time. Consider a knapsack problem 

Items as (value, weight) pairs
  {{60, 10}, {100, 20}, {120, 30}}
  Knapsack Capacity, W = 50

Our objective is to best fit the knapsack without exceeding the capacity of it.

Now, a correct solutions are all those which are in accordance with the facts i.e. say

20,30  Value - 100+120 = 220. It's a correct solution as it is not exceeding the knapsack capacity (But not optimal one)

Now take 10,20 and 2/3^rd of 30. Value = 240. It's a correct as well as optimal as it not only satisfies the facts but the objective function reaches it's maximum value (We wanted 'value' parameter to be maximized)

If they wanted to talk about time, they would have mentioned as faster, etc

Answer 1

If we compare greedy paradigm with dynamic programming we will see that the former first makes a choice and on the basis of that choice we move forward based on our assumption that the choice which we had made in the first position was correct. Where as in the case of Dynamic Programming first the computations are made and then we make a choice based on our "computations".

Coming to the statement:"Unlike greedy algorithms, dynamic programming method always provide correct/optimal solution.", if we consider the case of a multistage graph problem the answer which we get by the greedy approach is not always the correct answer, but dynamic programming efficiently solves this problem using memoization technique.

If by optimal solution we mean that the solution provided to us is correct then the given statement is correct.