(a)
To discuss the greedy
(a)
Explanation of Solution
To prove that the changing problem of coin has an optimal solution, take ' n ' cent and suppose, for these ' n ' cent changes, there is an optimal solution. The solution takes a coin with value ' c ' and uses ' k ' coins. If the solution of ' n-c ' cent changes problem lies within the solution of ' n ' cent problem solution, that means ' k-1 ' coins are available for ' n-c ' cents. So, take the solution for the ' n-c ' cent changing problem and make sure this should be lesser then ' k- 1 ' coins then figure out the solution for ' n ' cent problem.
While dealing with ' n ' cent problem and try to get an optimal solution by taking minimum no. of coins. Always provide the biggest denomination coin until the rest amount became zero. So, if there is the biggest denomination present at first then by applying greedy methodology changes in quarter, dime, nickel and pennies are:
Q = ⌊ n /25 ⌋ quarter that gives nQ = n mod 25 cent for change.
D = ⌊ nQ /10 ⌋ dimes that gives nD = nQ mod 10 cent for change.
K = ⌊ nD /10 ⌋ dimes that gives nK = nD mod 5 cent for change.
P = nK pennies
By seeing the greedy solution, there are few possibilities like:
- If n = 0; then zero coins in optimal solution.
- If n > 0; then get the biggest denomination with value = ' n ' , suppose it’s ' c ' .
- Now, take a coin and apply process in recursive manner for ' n-c ' cent.
To get the optimal solution through greedy algorithm, one must hold the coin ' c ' with value greater than ' n ' .
There are four cases needs to be considered here:
- If (1= n < 5) then c = 1, this must hold the greedy choice and contains pennies.
- If (5 = n = 10) then c = 5, by supposition, in this it must hold pennies and change 5 pennies to one nickel because this solution is not holding any nickel.
- If (10 = n = 25) then c = 10, by supposition, it must hold a nickel and pennies but not a dime. So, add a dime in the solution.
- If (25 = n ) then c = 25, by supposition, it holds a dime, pennies, and nickel but not quarter. If it has three dimes change it with a quarter and nickel and if has at least two dime then few subset of nickel, dime and pennies add nearly 25 cents and change these coins with a quarter to get a solution.
Here, for showing that it must contains an optimal solution with greedy choices and these choices will further helpful to get the solution of sub problem. Therefore, this greedy approach provides an optimal outcome for the given problem.
For an algorithm that selected a coin and recurses sub problem one by one, the running complexity will be θ ( k ), where ' k ' is the coins used for optimal solution. Now ( k = n), so, running time will be O ( n ) and there is only four type of coins. So, it requires O (1) constant time.
(b)
To show that for given denomination ( c0, c1, c2, ........., ck ), greedy algorithm always gives an optimal solution where ( c > 1) and (1 = k ).
(b)
Explanation of Solution
Take denomination c0, c1, c2, ........., ck and changes amount ' n ' . By taking this, it is clear that
Only few coins are required in changing coin to give an optimal solution. Apply greedy algorithm, take biggest denomination coin first means take a denomination ci (not ck ), where ( k>i ).
- To make sure that solution should be optimal take any denomination ( ci ) no. of coin that must be lesser then ' c ' .
- Take coins of ' ci ' denomination having ( x0, x1, ...., xk ) optimal solution and prove that for every ( k >i ), denomination ( c >xi ).
- And for few j , ( c = xi ) and change denomination coins cj with cj+1coin .
- Therefore, xj reduced by c, xj +1 increased by 1 and total no. of coins reduced by c -1.
This is contradicting about ( x0, x1,....., xk ) being a solution. So, that optimal solution should have denomination ' c ' greater than xi for any ' ci ' denomination.
Thus the only solution of the given problem is xk = n/ck ; for ( k>i ), xi = n mod ci +1/ ci . Therefore this is proved that greedy algorithm with ( c0, c1, c2, ........., ck ) denomination always gives an optimal solution.
(c)
To prove that greedy algorithm does not provides the optimal solution all the time.
(c)
Explanation of Solution
Take the denomination set as {1, 3, 4} and the value of ' n =6’.
Then greedy solution will give two one cent coin {1, 1} and a four-cent coin {4} like {1, 1, 4} but two coins as {3, 3} is optimal solution.
So, for the set {1, 3, 4}, optimal solution will not present by using greedy algorithm.
In the other example where denomination set contains value {1, 10, 25}, for ' n = 30’; greedy algorithm provide a quarter and five pennies {25, 1, 1, 1, 1, 1} but the optimal solution should be three dime like {10, 10, 10}.
Thus, greedy algorithm will not provide an optimal solution always.
(d)
To show that the time complexity of the algorithm is O ( nk ), where ' k ' is the total no. of coins.
(d)
Explanation of Solution
While applying the dynamic programming, take the demonstration ' d ' define as d1 , d2 , d3 ,...., dk and to make changes for ' i ' cent, no. of coins required min( c [ i ]). So, the minimum coins required can be calculated as:
c [ i ] = 1 + min{ c [ i-dj ]}, if ( i > 0) and (1 = j = k ),
c [ i ] = 0, if ( i = 0)
This formula should be implemented as,
MakeChange ( d,n )
- For ( i ← 1) to n
- Do c [ i ] ← 8
- For ( j ← 1) to k
- Do if ( dj = i )
- Then if c [ i ] > c [ i-dj ] + 1
- Then c [ i ] ← c [ i - dj ] + 1
- denom[ i ] ← dj
- Return demon and ' c '
By seeing the algorithmic procedure of MakeChange( d,n ), it is showing that it requires two loops up to ' n ' times as outer loop and ' k ' times as inner loop.
Thus, the complexity of the implementation will be O ( nk ).
Want to see more full solutions like this?
Chapter 16 Solutions
Introduction to Algorithms
- You have m dollars and a group of n friends. For each friend 1 ≤ i ≤n, you know the price P[i] of the piece of candy that would make your friend happy. You want to find a way to distribute the m dollars such that as many of your friends as possible are happy. Design an O(n log n) time greedy algorithm to find how much money you will allocate each friend.arrow_forwardAssuming you possess a total of 'm' dollars, and are accompanied by a group of 'n' friends. For every friend i, where i ranges from 1 to n, the price P[i] of the candy that would bring contentment to the respective friend is known. The objective is to devise a method for allocating a sum of m dollars in a manner that maximizes the number of contented friends. Propose an O(n log n) time greedy algorithm for determining the monetary allocation to be assigned to each friend.arrow_forwardAssume that you were given N cents (N is an integer) and you were asked to break up the N cents into coins consisting of 1 cent, 6 cents and 7 cents. Prove that a greedy algorithm may not always give the optimal solution.arrow_forward
- There are n people who want to carpool during m days. On day i, some subset si ofpeople want to carpool, and the driver di must be selected from si . Each person j hasa limited number of days fj they are willing to drive. Give an algorithm to find a driverassignment di ∈ si each day i such that no person j has to drive more than their limit fj. (The algorithm should output “no” if there is no such assignment.) Hint: Use networkflow.For example, for the following input with n = 3 and m = 3, the algorithm could assignTom to Day 1 and Day 2, and Mark to Day 3. Person Day 1 Day 2 Day 3 Limit 1 (Tom) x x x 2 2 (Mark) x x 1 3 (Fred) x x 0arrow_forwardAssume that you were given N cents (N is an integer) and you were asked to break up the N cents into coins consisting of 1 cent, 2 cents, and 5 cents. Prove that a greedy algorithm always gives the optimal solution.arrow_forwardSuppose we have n pieces of candy with weights W[1 .. n] (in ounces) that we want to load into boxes. Our goal is to load the candy into as many boxes as possible, so that each box contains at least L ounces of candy. Describe an efficient 2-approximation algorithm for this problem. Prove that the approximation ratio of your algorithm is 2. [Hint: First consider the case where every piece of candy weighs less than L ounces.]arrow_forward
- (a) A student has been asked to put some parcels on a shelf. The parcels all weigh different amounts, and the shelf has a maximum safe loading weight capacity of 100 Kg. The weight of parcels are as follows (in kg): parcel 1 2 3 4 5 6 7 weight (kg) 8 50 2 15 4 5 20 The student has been asked to load the maximum weight possible parcels on the shelf subject to the maximum safe loading weight. State two possible approaches for a greedy algorithm solution to solve this problem. In each case, state clearly the result you would get from applying that approach to this problem, stating whether the solution is optimal or not. If 4 your answer does not produce an optimal solution, what algorithm could be emploved to find one?arrow_forwardSuppose you have coins of denominations 1, 3 and 4. You use a greedy algorithm, in which you choose the largest denomination coin which is not greater than the remaining sum. For each of the following sums, just write YES if it will produce an optimal solution or NO if it won't. For example, for the sum 200, it will produce an optimal solution. For 14: For 6: For 10: For 100:arrow_forwardLet's say there are n villages, {X1, . . . , Xn} on the country-road and we aim to build K < n restaurants to cover them. Each restaurant has to be built in a village, and we hope to minimize the average distance from each village to the closest restaurant. Please give an algorithm to compute the optimal way to place these K restaurants. The algorithm should run in O(k * n^2) time. Solutions with slightly higher time complexity also accepted.arrow_forward
- group of n people are lying on the beach. The beach is represented by the real line R and the location of the i-th person is some integer x; e Z. Your task is to prevent people from getting sunburned by covering them with umbrellas. Each umbrella corresponds to a closed interval I = [a, a+ L] of length Le N, and the i-th person is covered by that umbrella if r; e I. Design a greedy algorithm for covering all people with the minimum number of umbrellas. The input consists of the integers x1,..., Xn, and L. The output of your algorithm should be the positions of umbrellas. A For example, if the input is x1 = 1, x2 = 3, x3 = 5, and L = 2, then an optimum solution is the set of two umbrellas placed at positions 2 and 5, covering intervals [1,3] and [4, 6]. %3D %3! %3D 3 4 5 6 1 2 The running time of your algorithm should be polynomial in n.arrow_forwardRoses 1 2 3 4 5 Profit $5 $15 $24 $30 $35 For each positive integer n, let f(n) be the maximum profit that Flora can make with n roses.For example, if n = 10, Flora can make numerous bouquet combinations, including two 5-rose bouquets (total profit of $70), and a 4-rose bouquet with three 2-rose bouquets (total profit of $75). Provide two different algorithms for calculating f(n): one using Recursion, and one using Dynamic Programming. Explain why both algorithms are guaranteed to return the correct value of f(n).arrow_forwardThe classic example of following a greedy algorithm is making change. Let’ssay you buy some items at the store and the change from your purchase is63 cents. How does the clerk determine the change to give you? If the clerkfollows a greedy algorithm, he or she gives you two quarters, a dime, andthree pennies. That is the smallest number of coins that will equal 63 cents(given that we don’t allow fifty-cent pieces).It has been proven that an optimal solution for coin changing can alwaysbe found using the current American denominations of coins. However, if weintroduce some other denomination to the mix, the greedy algorithm doesn’tproduce an optimal solution.Write a program that uses a greedy algorithm to make change (this codeassumes change of less than one dollar):arrow_forward
- Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill EducationStarting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSONDigital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
- C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSONDatabase Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage LearningProgrammable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education