// http://uva.onlinejudge.org/external/1/147.html
// @BEGIN_OF_SOURCE_CODE
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <sstream>
#include <set>
#include <cmath>
#define N 1000000
using namespace std;
int main ()
{
int coins [] = {1, 2, 4, 10, 20, 40, 100, 200, 400, 1000, 2000};
double dp [6000 + 10];
memset (dp, 0, sizeof (dp));
dp [0] = 1;
for ( int i = 0; i < 11; i++ ) {
for ( int j = 1; j <= 6000; j++ ) {
if ( j - coins [i] >= 0 )
dp [j] += dp [j - coins [i]];
}
}
double c;
while ( scanf ("%lf", &c) ) {
if ( c == 0 ) break;
int index = c * 20;
printf ("%6.2lf%17.lf\n", c, dp [index]);
}
return 0;
}
// @END_OF_SOURCE_CODE

### Like this:

Like Loading...

*Related*

## Published by Shahab

Completed B.Sc in CSE, @United International University, Dhaka.
Currently working as Development Engineer, Android and iOS Application.
View all posts by Shahab

can you explain why you have coins as 1,2,4, 10 ….. not 5c, 10c, 20c ……?

and why multiply by 20 the amount?

@Aslan Naurzbai

for the ease of calculation.

Let me explain, the lowest amount is 5c .. so we need to multiply all the numbers by 20 to make the lowest coin a full number 1

in this way, we will be able to work with only integers and no fraction part will bother us

from your above dp program , below is the the recursion formula , but it also counts the subsets which are same in value but order is different. how the above program is taking care of that :

int f2(int S , vector sol)

{

if(S == 0) { return 1;} /*does make a solution*/

if(S < 0) return 0; /*does not make a solution*/

int count =0;

/* try out each option from V */

for(int i=0; i< 3 ;i++){

count += f2(S – V[i]);

}

return count;

}