Question

1. Purpose: Apply various algorithm design strategies to solve a problem, practice formulating and analyzing algorithms, implement an algorithm. In the US, coins are minted with denominations of 50, 25, 10, 5, and 1 cent. An algorithm for making change using the smallest possible number of coins repeatedly returns the biggest coin smaller than the amount to be changed until it is zero. For example, 17 cents will result in the series 10 cents, 5 cents, 1 cent, and 1 cent.

a) (4 points) Give a recursive algorithm that generates a similar series of coins for changing n cents. Don’t use dynamic programming for this problem.

b) (4 points) Write an O(1) (non-recursive!) algorithm to compute the number of returned coins.

c) (1 point) Show that the above greedy algorithm does not always give the minimum number of coins in a country whose denominations are 1, 6, and 10 cents.

d) (6 points) Given a set of arbitrary denominations C =(c₁,...,c_d), describe an algorithm that uses dynamic programming to compute the minimum number of coins required for making change. You may assume that C contains 1 cent, that all denominations are different, and that the denominations occur in in increasing order.

Answer 1

1.

// Returns true if there is a subset of set[] with sun equal to given sum
int isSubsetSum(int set[], int n, int sum)
{
// Base Cases
if (sum == 0)
return 1;
if (n == 0 && sum != 0)
return 0;

if (set[n-1] > sum) // If last element is greater than sum, then ignore it
return isSubsetSum(set, n-1, sum);


//excluding //including
return 1+ min(isSubsetSum(set, n-1, sum),isSubsetSum(set, n-1, sum-set[n-1]));
}

Time Complexity = O(sum^n), where n is the number of coins given

Space Complexity: O(sum) for the recursion call stack.

2. Using greedy

#include<bits/stdc++.h>

using namespace std;
int main()
{   
int d;
cin>>d;
vector<int>deno;
for(int i=0;i<d;i++){
int e;
cin>>e;

deno.push_back(e);

//NOTE HERE I INSER DATA IN SORTING ORDER. EX.{1,5,10,20,50....}.{1,5,6,9} //if input data is not in sorting order then we have to sort data

}
  
int V;
vector<int> res;
cin >> V;
  
for (int i = d-1 ; V != 0; i--)
{
while (V < deno[i]) i--;
res.push_back(deno[i]);
V -= deno[i];
//cout << "V : " << V << endl;
i++;
}
  for (int i = 0; i < res.size(); i++)
cout << res[i] << " ";
    cout << endl;
  return 0;
}

• Time Complexity: O(V).
• Auxiliary Space: O(1) as no additional space is used.

3. in will fail in if i isert input {1,5,6,9}.then output will be {9,1,1} but output should be {5,6}.so greedy does not work here.

Note: you can try with insert input in above programm.

4.

Dynamic programming solve the greedy problem.

#include<bits/stdc++.h>

using namespace std;

int F(int *coins, int n, int sum)
{
int dp[n+1][sum+1];
  
for(int i = 0; i <= n; i++) {
for(int j = 0; j <=sum; j++) {
dp[i][j] = 1000000;
}
}
for(int i=0;i<=n;i++){
dp[i][0]=0;
}
  
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= sum; j++)
{
if(j < coins[i-1]) dp[i][j] = dp[i-1][j];
else
{
  dp[i][j] = min(dp[i-1][j], 1 + dp[i][j-coins[i]]);
  }
}
}
if(dp[n][sum] == 1000000) dp[n][sum] = -1; //Not possible to make sum from these coins
return dp[n][sum];
}

int main() {
   int t;
   cin>>t;
   while(t--)
   {
   int n,sum;
   cin>>sum>>n;
   int *arr = new int[n+1];
   for(int i = 1; i <= n; i++){
   cin>>arr[i]; //insert coins
   }
   sort(arr+1,arr+n+1); //If coins are not in sorted order then we have to sort them.
     cout<<F(arr, n, sum)<<endl;
   }
   return 0;
}

Time complexity of the above solution is O(sum*n). // sum:is make a required sum and n is number of coin