Greedy algorithm vs dynamic programming

Greedy algorithms and dynamic programming are both techniques used in computer science for solving optimization problems, but they differ in their approach to finding the optimal solution.

Greedy algorithm

Greedy algorithms don't find the optimal solution but they find a good solution in a simpler way with less time complexity. If we don't care about the optimal solution we can use them. An example would be the Knapsack problem. If we want to maximise the value of items in our bag we need to use dynamic programming and test all the combinations to find the most valuable items we can fit in our bag while in the greedy approach, we can simply sort items based on value/weight ration and pick highest value items first. Obviously, in this approach, we might end up with some empty space in our bag but since this approach is much simpler it makes sense that for some applications we use this rather than the optimal solution.

Consider the following example:
Value of items: [1.65, 1, 1]
Weight of items: [3, 2, 2]
Value / Weight: [0.55, 0.5, 0.5]

If the maximum weight of our bag is 4, in the greedy approach we would pick the first item since it has the highest value/weight and there is no more room for any other items. In this case, we could fit an item with a value of 1.65 but the optimal solution to this problem is 2 if we pick the other two items.

Dynamic programming

Dynamic Programming (commonly referred to as DP) is an algorithmic technique for solving a problem by recursively breaking it down into simpler subproblems and using the fact that the optimal solution to the overall problem depends upon the optimal solution to its individual subproblems.

• DP algorithm solves each subproblem just once and then remembers its answer, thereby avoiding re-computation of the answer for similar subproblems every time.
• It is the most powerful design technique for solving optimization related problems.
• It also gives us a life lesson - Make life less complex. There is no such thing as a big problem in life. Even if it appears big, it can be solved by breaking it into smaller problems and then solving each optimally.

There are two techniques for solving a problem using dynamic programming:

• Top Down Approach (Memorization): recursive, cache the result of subproblems so we don't repeat those steps.
• Bottom-Up Approach (Tabulation): solve subproblems first, typically by population into an n-dimensional table.