Question

Consider the problem of making change for n cents using the fewest number of coins. Assume that each coins value is an integer. a. You have available coin denominations of 1 cent, 5 cents, 10 cents, 25 cents, as in the US coins of penny, nickel, dime, quarter. Assume there is infinite availability of each of these four coin denomination types. Describe a greedy algorithm to make change using the fewest number of coins. b. Consider your greedy algorithm and making change for n=30 cents. Show that the optimal solution for making change includes your greedy choice. To do so, assume that your greedy choice is not in the optimal solution. Then use the "cut and paste" argument to show that you can replace other coins by your greedy choice, therefore finding a better solution than what was assumed to be optimal. This is in contradiction to the assumption, so your greedy choice is in the optimal solution. c. Although the greedy algorithm is optimal for the US coins, it is not necessarily optimal for any set of coins. Give an example of a different set of made up coin denominations with different values, for which the greedy algorithm does not yield an optimal solution. Your set should include a penny so that there is a solution for every value of n. As before, assume there is infinite availability of each of the coin denomination types. Show specifically a counter example in which the greedy algorithm yields a change solution that is not optimal, that is, does not include the fewest number of coins. d. Name another algorithmic approach that will find an optimal solution to your example in (c).

Answer 1

Answer:

There are two algorithms in which apply different optimal solutions.

They are: A Dynamic and Naive recursive programs

Explanation:

// A Naive recursive C++ program to find minimum of coins  

// to make a given change V  

#include<bits/stdc++.h>  

using namespace std;  

// m is size of coins array (number of different coins)

int minCoins(int coins[], int m, int V)  

{  

// base case  

if (V == 0) return 0;  

// Initialize result

int res = INT_MAX;  

// Try every coin that has smaller value than V  

for (int i=0; i<m; i++)  

{  

if (coins[i] <= V)  

{  

 int sub_res = minCoins(coins, m, V-coins[i]);  

 // Check for INT_MAX to avoid overflow and see if  

 // result can minimized

 if (sub_res != INT_MAX && sub_res + 1 < res)  

  res = sub_res + 1;  

}  

}  

return res;  

}  

// Driver program to test above function  

int main()  

{  

int coins[] = {9, 6, 5, 1};  

int m = sizeof(coins)/sizeof(coins[0]);  

int V = 11;  

cout << "Minimum coins required is "

 << minCoins(coins, m, V);  

return 0;  

}  

.........................................

// A Dynamic Programming based C++ program to find minimum of coins  

// to make a given change V  

#include<bits/stdc++.h>  

using namespace std;  

// m is size of coins array (number of different coins)  

int minCoins(int coins[], int m, int V)  

{  

// table[i] will be storing the minimum number of coins  

// required for i value. So table[V] will have result  

int table[V+1];  

// Base case (If given value V is 0)  

table[0] = 0;  

// Initialize all table values as Infinite  

for (int i=1; i<=V; i++)  

 table[i] = INT_MAX;  

// Compute minimum coins required for all  

// values from 1 to V  

for (int i=1; i<=V; i++)  

{  

 // Go through all coins smaller than i  

 for (int j=0; j<m; j++)  

 if (coins[j] <= i)  

 {  

  int sub_res = table[i-coins[j]];  

  if (sub_res != INT_MAX && sub_res + 1 < table[i])  

   table[i] = sub_res + 1;  

 }  

}  

return table[V];  

}  

// Driver program to test above function  

int main()  

{  

int coins[] = {9, 6, 5, 1};  

int m = sizeof(coins)/sizeof(coins[0]);  

int V = 11;  

cout << "Minimum coins required is "

 << minCoins(coins, m, V);  

return 0;  

}