Greedy Approach

#1

Why does greedy approach work for some denominations and not for others (logically)? In such questons how do decide if we should use greedy or dp?

#2

Hello @drishti307,

  1. I understand how the greedy algorithm for the coin change problem (pay a specific amount with the minimal possible number of coins) works - it always selects the coin with the largest denomination not exceeding the remaining sum - and that it always finds the correct solution for specific coin sets of coins.

    But for some coin sets, there are sums for which the greedy algorithm fails. For example, for the set {1, 15, 25} and the sum 30, the greedy algorithm first chooses 25, leaving a remainder of 5, and then five 1s for a total of six coins. But the solution with the minimal number of coins is to choose 15 twice.

    Reason:
    In any case where there is no coin whose value, when added to the lowest denomination, is lower than twice that of the denomination immediately less than it, the greedy algorithm works.

    i.e. {1,2,3} works because [1,3] and [2,2] add to the same value however {1, 15, 25} doesn’t work because (for the change 30) 15+15>25+1

  2. Greedy Algorithm:

    An algorithm that always takes the best immediate, or local, solution while finding an answer. Greedy algorithms find the overall, or globally, the optimal solution for some optimization problems, but may find less-than-optimal solutions for some instances of other problems.

    Problems that can be solved by a Greedy Algorithm will have two properties:

  • Greedy Choice Property;
  • Optimal Substructure.

    Usually, the solutions for greedy problems require sorting.

    Dynamic Programming:

    Solve an optimization problem by caching subproblem solutions (memoization) rather than recomputing them.

    Dynamic Programming algorithms are often used for optimization because it will examine the previously solved subproblems and will combine their solutions to give the best solution for the given problem.

    Now, problems that can be solved by a Dynamic Programming Algorithm will have this necessary condition:

    Principle of Optimality: An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.

Hope, this would help.
Give a like if you are satisfied.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.