Post date: Aug 02, 2013 5:2:33 AM
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>
#include <vector>
using namespace std;
int FindWaysMakeX(int x)
{
int coins[] = {1, 2, 5, 10};
vector<int> dp(x + 1);
for(int i = 0; i < 4; ++ i){
for(int j = coins[i]; j <= x; ++j){
dp[j] += max(dp[j - coins[i]], 1);
}
}
return dp[x];
}
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 . . .