Problem
Given notes of different denominations ( 1,2,5,10) , WAP to find in how many ways can you make an amount ‘x’ ?
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find how many ways can you make an amount ‘x’
Created Date : 02-08-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
using namespace std;
int FindWaysMakeX(int x)
{
int count10 = x / 10;
int count5 = x / 5;
int count2 = x / 2;
int ways(0);
for(int i = 0; i <= count10; ++i){
for(int j = 0; j <= count5; ++ j){
if(i * 10 + j * 5 > x) break;
for(int k = 0; k <= count2; ++k){
if(i * 10 + j * 5 + k * 2 > x) break;
ways ++;
}
}
}
return ways;
}
int main(int argc, char* argv[])
{
for(int i = 0; i < 20; ++i){
cout << "X = " << i;
cout << " has " << FindWaysMakeX(i) << " ways" << endl;
}
return 0;
}
Output
X = 0 has 1 ways
X = 1 has 1 ways
X = 2 has 2 ways
X = 3 has 2 ways
X = 4 has 3 ways
X = 5 has 4 ways
X = 6 has 5 ways
X = 7 has 6 ways
X = 8 has 7 ways
X = 9 has 8 ways
X = 10 has 11 ways
X = 11 has 12 ways
X = 12 has 15 ways
X = 13 has 16 ways
X = 14 has 19 ways
X = 15 has 22 ways
X = 16 has 25 ways
X = 17 has 28 ways
X = 18 has 31 ways
X = 19 has 34 ways
Press any key to continue . . .