Answer to Question #285702 in C++ for tony

Question

Consider the problem of making change for N cents using the fewest number of coins. Assume that the coin set consists of c1, c2, …, cd; and each coin’s value is an integer. Write a greedy algorithm for that.

Sample input:

4

1 10 25 5

173

Sample output:

#25 cents --- 6

#10 cents --- 2

#1 cents --- 3

Total 11 coins

sample input:

2

3 5 16

sample output:

#5 cents --- 3

Opps! can’t form 16 taka

Answer 1

#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;


int main(){
    int size, amount;
    vector<int> coins;


    cin>>size;
    coins.resize(size);
    for(int i = 0; i < size; i++){
        cin>>coins[i];
    }
    cin>>amount;


    sort(coins.begin(), coins.end());


    int t_amount = amount, t_numcoins = 0;
    for(int i = size - 1; i >= 0; i--){
        if(t_amount >= coins[i]){
            int numcoins = t_amount / coins[i];
            cout<<"#"<<coins[i]<<" cents -- "<< numcoins <<endl;
            t_amount %= coins[i];
            t_numcoins += numcoins;
        }
    }


    if(t_amount == 0){
        cout<<"\nTotal "<<t_numcoins<<" coins\n";
    }
    else{
        cout<<"\nOops! can't form "<<amount<<" taka\n";
    }
    return 0;
}