Algorithm Greedy Vs Dynamic Programming Complete Guide

Introduction to Greedy and Dynamic Programming Algorithms

Greedy Algorithm:

• A greedy algorithm builds up a solution piece by piece, always choosing the next piece that offers the most immediate benefit.
• It focuses on making a locally optimal choice at each stage with the hope of finding the global optimum.
• Greedy algorithms are generally quicker to solve but don't always yield the best solution.

Dynamic Programming (DP):

• DP is a method used to solve complex problems by breaking them down into simpler subproblems and storing the results of these subproblems to avoid redundant computations.
• The key idea is to solve smaller instances of the problem first and use their solutions to construct the solution to the larger instance.
• DP is more suitable for optimization problems where a combination of optimal subproblems leads to an overall optimal solution.

Step-by-Step Example: Greedy Algorithm – Activity Selection Problem

Problem Statement:
You have a set of activities each associated with a start and end time. Select the maximum number of activities that can be performed by a single person, assuming a person can only work on a single activity at a time.

Steps:

1. Sort Activities:
   Sort all activities based on their end times in non-decreasing order.

2. Select First Activity:
   Include the first activity from the sorted list to the selected set.

3. Repeat Selecting Activities:
   For each subsequent activity:

   • If it starts after or when the last selected activity finishes, include it in the selected set.
   • Otherwise, exclude it.

Example:

Consider activities with the following start and finish times:

| Activity | Start Time | Finish Time | |--------------|----------------|-----------------| | A1 | 0 | 3 | | A2 | 1 | 4 | | A3 | 3 | 5 | | A4 | 0 | 6 | | A5 | 5 | 7 | | A6 | 8 | 9 | | A7 | 5 | 9 | | A8 | 6 | 10 | | A9 | 8 | 11 | | A10 | 2 | 13 |

1. Sort Activities Based on End Times: After sorting, the list becomes:

   | Activity | Start Time | Finish Time | |--------------|----------------|-----------------| | A1 | 0 | 3 | | A2 | 1 | 4 | | A3 | 3 | 5 | | A5 | 5 | 7 | | A6 | 8 | 9 | | A8 | 6 | 10 | | A9 | 8 | 11 | | A10 | 2 | 13 | | A4 | 0 | 6 | | A7 | 5 | 9 |

2. Select Activities Using Greedy Approach:

   • Start with the first activity A1 (finish time 3).
   • Check A2: Finish time is 4 (A2 cannot be selected since it starts before A1 ends).
   • Select A3 (starts at 3, which matches the finish time of A1).
   • Select A5 (starts at 5, which matches the finish time of A3).
   • Select A6 (starts at 8, which matches the finish time of A5).

3. Selected Activities:

   • A1, A3, A5, A6

Hence, the maximum number of activities that can be performed is 4.

Step-by-Step Example: Dynamic Programming – 0/1 Knapsack Problem

Problem Statement:
Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. Each item can either be selected or not (binary inclusion).

Steps:

1. Define Subproblems:
   Define a 2D array dp[i][w], where i is the number of items and w is the weight capacity of the knapsack. dp[i][w] will store the maximum value that can be obtained with the first i items and a knapsack capacity of w.

2. Build a Bottom-Up DP Table: Iterate through the items and fill the DP table using the following rule:

   • If including the i-th item does not exceed the current weight capacity w, then choose:

     dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w - weights[i-1]])
     

   • Otherwise, do not include:

     dp[i][w] = dp[i-1][w]
     

3. Result: The maximum value that can be put in a knapsack of capacity W will be present at dp[n][W].

Example:

Let's consider the following items and a knapsack capacity of W=50:

| Item | Weight | Value | |----------|------------|-----------| | i1 | 10 | 60 | | i2 | 20 | 100 | | i3 | 30 | 120 |

1. Initialize the DP Table: Create a 2D array dp[4][51] (since there are 3 items + 1 base case for 0 items).

   dp = [
       [0 for w in range(51)] for i in range(4)
   ]
   

2. Iterate Through Each Item and Capacity:

   • For i=0 (base case, no items), dp[0][w] = 0 for all w.
   • For i=1 (item i1):
     • For each w from 1 to 50:
       • If w < 10, dp[1][w] = dp[0][w] (item cannot be included).
       • If w >= 10, compare:
         • Without item i1: dp[0][w]
         • With item i1: 60 + dp[0][w - 10]

         dp[1][w] = max(0 + dp[0][w], 60 + dp[0][w - 10])
         

   Similar steps are followed for i=2 (item i2) and i=3 (item i3).

3. Fill the DP Table (Detailed Computation): Here’s the computation for few capacities for better understanding:

   i\w | 0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20 ...
   ----------------------------------------------------------------------------
   dp[0]| 0  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0
   dp[1]| 0  0  0  0  0  0  0  0  0  0  60  60  60  60  60  60  60  60  60  60
   ...
   dp[2]| 0  0  0  0  0  0  0  0  0  0  60  60  60  60  60  60  60  60  60  60
          ...
          | 160 160 160 160 160 160 160 160 160 160 160 160 160 **220** ...
   ...
   dp[3]| ...
          ...
          | ... **220** **240** ... **240** **260** ...
   ...
   

4. Extract the Maximum Value: The maximum value achievable with the knapsack capacity of 50 (all items considered) will be at dp[3][50], which turns out to be 220.

Comparison of Greedy vs Dynamic Programming

Greedy Algorithm Pros:

• Simpler and easier to implement.
• Generally requires less memory.
• Faster in terms of computation time since decisions are made without considering future states.

Greedy Algorithm Cons:

• May not always result in the optimal solution.
• Local choices sometimes lead to globally suboptimal outcomes.

Dynamic Programming Pros:

• Guarantees finding the optimal solution by considering all possible configurations.
• Can be applied to a wider variety of problems.

Dynamic Programming Cons:

• Often more complex to design and implement.
• Requires more memory to store subproblem solutions.
• Can be slower due to overlapping subproblem evaluations.

Conclusion

Choosing between a greedy algorithm and dynamic programming depends on the problem at hand:

• Use a greedy approach when you know making a series of locally optimal choices yields a globally optimal solution.
• Use dynamic programming for optimization problems where such local-to-global optimality is uncertain or impossible.

Understanding when and how to apply each strategy is crucial both for solving specific problems and for developing efficient algorithms in general scenarios.