Greedy Algorithms

Created by Thang Vu

Definition

An algorithm is said to be greedy if it makes the locally optimal choice at each step with the hope of eventually reaching the globally optimal solution. 

In some cases, greedy works, the solution is short and runs efficiently. For many others, however, it does not. 

A problem must exhibit these two properties in order for a greedy algorithm to work:

• It has optimal sub-structures. Optimal solution to the problem contains optimal solutions to the sub-problems.
• It has the greedy property. If we make a choice that seems like the best at the moment and proceed to solve the remaining subproblem, we reach the optimal solution. We will never have to reconsider our previous choices. 

Elements of the greedy strategy

To develop a greedy algorithm, we go through the following steps:

1. Cast the optimization problem as one in which we make a choice and are left with one subproblem to solve.
2. Prove that there is always an optimal solution to the original problem that makes the greedy choice, so that the greedy choice is always safe. 
3. Demonstrate optimal substructure by showing that, having made the greedy choice, what remains is a subproblem with the property that if we combine an optimal solution to the subproblem with the greedy choice we have made, we arrive an optimal solution to the original problem. 

Greedy versus dynamic programming

Both greedy and dynamic programming strategies exploit optimal substructure. In greedy algorithm, we can assemble a globally optimal solution by making locally optimal choices. In more detail, we make the choice that looks best in the current problem, without considering results from subproblems. In dynamic programming, we make a choice at each step, but the choice usually depends on the solutions to the problem. 

Coin change problem

Problem discription: Given a target amount V cents and a list of denominations of n coins, i.e. we have coin_value[i] (in cents) for coin types i = 1..n-1, what is the minimum number of coins that we must use to represent amount V? Assume that we have an unlimited supply of coins of any type.
Example: if n = 4, coin_value = {25, 10, 5, 1} cents, and we want to represent V = 42 cents, we can use this Greedy algorithm: Select the largest coint denomination wich is not greater than the remaining amount, i.e. 42 - 35 = 17 , 17 - 10 = 7 ,  7 - 5 = 2 ,  2 - 1 = 1,  1 - 1 = 0., a total of 5 coins. This is optimal.

The problem above has the two ingredients required for a successful greedy algorithm.

• It has optimal substructures: We have seen that in our quest to represent 42 cents, we used 25 + 10 + 5 + 1 + 1. This is an optimal 5-coin solution to the original problem. i.e. to present 17 cents we can use 10 + 5 + 1 + 1 (part of the solution for 42 cents), to represent 7 cents, we can use 5 + 1 + 1 (also part of te solution for 42 cents).
• It has the greedy property: Given every amount V, we can greedily subtract from it the largest coin denomination which is not greater than this amount V. It can be proven that using any other strategies will not lead to an optimal solution, at least for this set of coin denominations. 

The following is the C code for the example.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

#include <stdio.h> #define COIN_TYPE 4   int main() {  int coin_value[COIN_TYPE] = {25, 10, 5, 1};  int total_value,i;  printf("%s\n", "Enter total value: ");  scanf("%d", &total_value);  printf("%s", "Selected coins are: ");  while ( total_value > 0) {   for (i = 0; i < COIN_TYPE; i++) {    if( total_value >= coin_value[i]){     total_value -= coin_value[i];     printf("%d\n", coin_value[i]);     break;    }   }  }  return 0; }

However, this greedy algorithm does not work for all sets of coin denominations. Take for example {4, 3, 1} cents. To make 6 cents with that set, a greedy algorithm would choose 3 coins {4, 1, 1} instead of the optimal solution that uses 2 coins {3, 3}.

Station balance problem

Given 1 <= C <= 5 chambers which can store 0, 1, or 2 specimens, 1 <= S <= 2c specimens and a list M of the masses of the S specimens, determine which chamber should store each specimen in order to minimize imbalance. 

Denote A the average of the total mass in each of the C chambers. The imbalance is the sum of differences between the actual total mass in each chamber and the average total mass.

If S > C, then S - C specimans must be paired with a chamber already containing other specimens. So we create dummy specimens with mass 0. And use greedy algorithm to out specimens into each chambers. 

C code for this example:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

#include <stdio.h> #include <math.h> #define NUM_SPE 5   //number of specimens #define NUM_CHB 3   //number of chambers int specimens[NUM_SPE] = {5, 1, 2, 7, 6}; int optimal[2 * NUM_CHB];   void sort(int array[]) {  int i, j;  for (i = 0; i < NUM_SPE; i++) {   for (j = i + 1; j < NUM_SPE; j++) {    if (array[i] < array[j]) {     int temp = array[i];     array[i] = array[j];     array[j] = temp;    }   }  } } int main() {  int i;  sort(specimens);  for ( i = 0; i < NUM_CHB; i++) {   printf("Chamber %d has %d ", i, specimens[i]);   if (2 * NUM_CHB - i <= NUM_SPE) {    printf("and %d\n", specimens[2 * NUM_CHB - i - 1]);   } else {    printf("\n");   }  }  return 0; }

Huffman code

Huffman invented a greedy algorithm that constructs an optimal prefix code called a Huffman code. Huffman codes compress data very effectively: savings of 20% to 90% are typical. Suppose that we have a 100,000 character data that we wish to store compactly, we observe that the character in the file occur with the frequencies given by the following figure. 

If we ned 3 bits to represent 6 characters: a = 000, b = 001, ..., f = 101. This method requires 300,000 bits to code the entire file.

The idea of Huffman code is giving frequent characters short codewords and infrequent characters long codewords. As in the above figure, the total bits are only 224,000. To enable to decompress Huffman code, each codeword must not be the prefix of the others. To generate code word we can use a binary tree as follow with assumption that the left (right) child node is corresponding to bit 0 (bit 1). 

References

Steven Halim, Felix Halim, "Competitive programming", handbook for ACM ICPC and IOI contestants 2013

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, "Introduction to Algorithm", Third edition.