Consider the change-making problem by giving change for a specific amount n with the least number of coins of the denominations d1 > d2 > … > dm .
·An example: Let the coin denominations be d1 = 25 (quarter), d2 = 10 (dime), d3 = 5 (nickel), and d4 = 1 (penny). ·How would you give change with coins of these denominations of, say, 48 cents? oGreedy technique comes up with the answer 1 quarter, 2 dimes and 3 pennies. o“Greedy” thinking leads to giveone quarterbecause it reduces the least remaining amount to 23 cents. oThe best selection in the next step isone dime, reducing the least remaining amount to 13 cents. oGivingone more dimereduce the least remaining amount to 3 cents which are to be given withthree pennies.
PowerPoint Presentation Chapter 07 Greedy Algorithms Greedy Technique Consider the change-making problem by giving change for a specific amount n with the least number of coins of the denominations d1 > d2 > … > dm . An example: Let the coin denominations be d1 = 25 (quarter), d2 = 10 (dime), d3 = 5 (nickel), and d4 = 1 (penny). How would you give change with coins of these denominations of, say, 48 cents? Greedy technique comes up with the answer 1 quarter, 2 dimes and 3 pennies. “Greedy” thinking leads to give one quarter because it reduces the least remaining amount to 23 cents. The best selection in the next step is one dime, reducing the least remaining amount to 13 cents. Giving one more dime reduce the least remaining amount to 3 cents which are to be given with three pennies. Greedy Technique Consider the change-making problem by giving change for a specific amount n with the least number of coins of the denominations d1 > d2 > … > dm . An example: Let coin denominations be d1 = 25 (quarter), d2 = = 10 (dime), d3 = 5 (nickel), and d4 = 1 (penny). Using Greedy Technique, how would you give change with coins of these denominations of, say, 48 cents? Using 1Q first, 48 – 25 = 23 Using 1D, 23 – 10 = 13 Using 1D, 13 – 10 = 3 Using 1P, 3 – 1 = 2 Using 1P, 2 – 1 = 1 Using 1P, 1 – 1 = 0 Conclusion: Using 1Q, 2D and 3P (6 items.) Dynamic Programming Consider the same change-making problem by giving change for a specific amount n with the least number of coins of the denominations d1 > d2 > … > dm . An example: Let coin denominations be the same, d1 = 25 (quarter), d2 = = 10 (dime), d3 = 5 (nickel), and d4 = 1 (penny). Using dynamic programming, how would you give change with coins of these denominations of, say, 48 cents? Using dynamic programming, apply the following formula: F(n) = minj: n ≥dj { F(n – dj ) } + 1 for n > 0 …………… 8.4 F(0) = 0. The solution is F(48) = min{F(48-1), F(48-5), F(48-10), F(48-25)} + 1 = F(47) + 1 or F(38) + 1 or F(23) + 1 = {{1Q, 2 D, 2 P} + {1P}} or {{1Q, 1D, 3P} + {1D}} or {{2D, 3P} + {1Q}} = {1Q, 2D, 3P} n01234567891011…232425…38…43…4748 F(n)0123412345125615656 Greedy Technique Is the solution to the instance of the change-making problem optimal with respect to these given coins denominations? For greedy technique, yes, it is. We can prove that the greedy algorithm yields an optimal solution for every positive integer amount n with these coins denominations, d1 = 25 (quarter), d2 = = 10 (dime), d3 = 5 (nickel), and d4 = 1 (penny). The dynamic programming yields an optimal solution to the instance of the change-making problem. Greedy Technique Given the coin denominations, e.g., d1 = 25 (quarter), d2 = = 10 (dime), and d3 = 1 (penny), the greedy algorithm does not yield an optimal solution to the instance of the change-making problem for some amounts, say n = 30 cents. Using Greedy thinking, it leads to 1 quarter and 5 pennies. Using 1Q, 30 – 25 = 5 Using 1P, 5 – 1 = 4 Using 1P, 4 – 1 = 3 Using 1P, 3 – 1 = 2 Using 1P, 2 – 1 = 1 Using 1P, 1 – 1 = 0 But the optimal solution is 3 dimes. Dynamic Programming With this coins of these denominationsd1 = 25 (quarter), d2 = 10 (dime), and d3 = 1 (penny), the dynamic programming yields an optimal solution for giving change for n = 30 cents, Using dynamic programming, apply the following formula: F(n) = minj: n ≥dj { F(n – dj ) } + 1 for n > 0 …………… 8.4 F(0) = 0. The solution is F(30) = min{F(30-1), F(30-10), F(30-25)} + 1 = min{F(29) , F(20) , F(5) }+ 1 = min{{1Q, 4P}, {2D}, {5P}} + 1 ={2D} + {1D} n012345………20…2930 F(n)012345256 How would you give change with coins of these denominations of, say, n = 30 cents, if the coins denominations are again d1 = 25 (quarter), d2 = = 10 (dime), d3 = 5 (nickel), and d4 = 1 (penny)? The greedy technique leads to 1 quarter and 1 nickel, which is an optimal solution. Using 1Q30 – 25 = 5 Using 1N 5 – 5 = 0 The greedy algorithm yields an optimal solution for every positive integer amount with these coins denominations. Dynamic Programming Given these donominations, d1 = 25 (quarter), d2 = = 10 (dime), d3 = 5 (nickel), and d4 = 1 (penny), the dynamic programming applies the following formula to give change with coins of these denominations of n = 30 cents F(n) = minj: n ≥dj { F(n – dj ) } + 1 for n > 0 …………… 8.4 F(0) = 0. The solution is F(30) = min{F(30-1), F(30-5), F(30-10), F(30-25)} + 1 = min{F(29) , F(25), F(20) , F(5) }+ 1 = min{{1Q, 4P}, {1Q}, {2D}, {1N}} + 1 ={1Q} + {1N} n012345……20…25…2930 F(n)0123452156 The greedy approach suggests constructing a solution through a sequence of steps, each expanding a partially constructed solution obtained so far, until a complete solution to the problem is reached. The central point of this technique is that on each step, the choice made must be: Feasible it has to satisfy the problem’s constraints Locally optimal it has to be the best local choice among all feasible choices available on that step Irrevocable once made, it cannot be changed on subsequent steps of the algorithm. The central point of the greedy approach An example A problem of placing the maximum number of chips on an 8 x 8 board so that no two chips are placed on the same squares or adjacent vertically, horizontally, or diagonally squares. For the greedy strategy, place each new chip so as to leave as many available squares as possible for next chips. For example, starting with the upper left corner of the board, we will be able to place 16 chips as shown in Figure 9.1(a). Why is this solution optimal? The final result obtained via a greedy algorithm is optimal based on the algorithm’s output rather than the way it operates. Greedy Technique Greedy Technique: Placement of 16 chips on non-adjacent squares. Figure 9.1(a) Placement of 16 chips on non-adjacent squares. Violates the restriction Figure 9.1 (b) Partition of the board proving impossibility of placing more than 16 chips. Why is this solution optimal? The reason is: Partition the board into sixteen 4x4 squares as shown in Figure 9.1b. Total number of nonadjacent chips on the board cannot exceed 16 since it is impossible to place more than one chip in each of these squares. An example for proving optimality of a greedy algorithm is to show that on each step it does at least as well as any other algorithm could in advancing toward the problem’s goal. Greedy Technique Greedy Technique Find the minimum number of moves for a chess knight to go from one corner of a 100x100 board to the diagonally opposite corner. Requirement: The knight’s moves are L-shaped jumps: goes forward two(2) squares horizontally or vertically and then goes forward one(1) square vertically or horizontally, respectively.) A greedy solution is: jump as close to the goal as possible on each move. If it starts from the square (1, 1) and finishes at the (100, 100), it requires a sequence of 66 moves such as (1, 1), (3, 2), (4, 4), (6, 5), (7, 7), (9, 8), (10, 10), (12, 11), …, (97, 97), (99, 98), (100, 100) Greedy Technique Find