Greedy algorithms

Greedy strategy for coin change

Given n types of coins, where the denomination of the ith type of coin is coins[i−1], and the target amount is amt, with each type of coin available indefinitely, what is the minimum number of coins needed to make up the target amount? If it is not possible to make up the target amount, return −1.

Given the target amount, we greedily choose the coin that is closest to and not greater than it

int coinChangeGreedy(vector<int> &coins, int amt)
{
    int i = coin.size() - 1;
    int count = 0;
    //Loop for greedy selection until no remaining amount
    while(amt > 0)
    {
        //Gradually find smallest coin close to and less than the remaining amount
        while(i > 0 && coins[i] > amt)
        {
            i--;
        }
        amt -= coins[i];
        count++;
    }
    //If no solution, return -1
    return amt == 0 ? count : -1;//即要么是count要么是-1
}

It is really clean, just few lines solving this problem. Not only simple and straightforward, but also efficient.

If the smallest coin denomination is min(coins), the loops at most $amt/min(coins)$, so its time complexity is $O(amt/min(coins))$.

This is an order of magnitude smaller than the time complexity of the dynamic programming solution, with $O(n \times amt)$.（比动态算法小了一个数量级）

Examples where greedy algorithms do not find the optimal solution

For this picture we can see, sometimes greedy solution cannot be the optimal solution, compared to Dynamic programming.

So the sutability of greedy algorithms falls into two categories.

Guaranteed to find the optimal solution: In these cases, greedy algorithms are often the best choice, as they tend to be more efficient than backtracking or dynamic programming.
Can find a near-optimal solution: Greedy algorithms are also applicable here. For many complex problems, finding the global optimal solution is very challenging, and being able to find a high-efficiency suboptimal solution is also very commendable.

Characteristics of greedy algorithms

Under what conditions can greedy algorithms guarantee to find the optimal solution?

The conditions will be more stricter!

Greedy choice property: Only when the locally optimal choice can always lead to a globally optimal solution can greedy algorithms guarantee to obtain the optimal solution.
Optimal substructure: The optimal solution to the original problem contains the optimal solutions to its subproblems.

Steps for solving problems with greedy problems

1.Problem analysis: Sort out and understand the characteristics of the problem, including state definition, optimization objectives, and constraints, etc.

2.Determine the greedy strategy: Determine how to make a greedy choice at each step. Namely reduce the scale of the problem.

3.Proof of correctness: prove that the problem has both a greedy choice property and optimal substructure.

Typical Problems

Coin change problems

Interval scheduling problem

Fractional knapsack problem

Stock trading problem

Huffmam coding

Dijkstra’s algorithm

Fractional knapsack problem

$Example data of the fractional knapsack problem$

This is the problem, wgt[i-1]are mapped to val[i-1]， there is a backpack with limited capacity, we should choose appropriate weight to reach the capacity, and the goods can be chosen the part of its weight. What is the maximum value of the items in the knapsack under the limited capacity?

We can first use $wgt[i-1] / val[i-1]$ to get the unit value, and if we want to add a part of item i into the knapsack, we should compute $w \times \frac{wgt[i-1]}{val[i-1]}$,namely using proportional relationship.

Value per unit weight of the item

greedy strategy determination

Because we want to find the maximum value of the total weight, so we should first find the order of the increasing unit value, like the picture below, then choosing the items with higher unit value.

$Greedy strategy of the fractional knapsack problem$