Saturday, April 20, 2013

Number of ways to change making (Dynamic Programming)

This is a variant of change making problem. Here, we are just asked to count the number of ways to make the specific change. With a little change to the change making problem's solution, we can solve this one. The problems which can be solved with the following solution are
UVa - 657 - Coin Change

UVa - 357 - Let Me Count The Ways (Need to change the way solution is printed as per problem description)

# include <iostream>
# include <cstdio>
using namespace std;
unsigned long long NumberOfWays [30001], Coins []= {1, 5, 10, 25, 50}, Num;
int main ()
{
 //freopen ("Input.txt", "r", stdin);
 //freopen ("Scratch.txt", "w", stdout);
 NumberOfWays[0] = 1;
 for (int i = 0; i < 5; i++)
  for (int j = Coins[i]; j < 30001; j++)
   NumberOfWays [j] += NumberOfWays [j - Coins[i]];
 while (scanf ("%lld", &Num) != EOF)
  printf ("%lld\n", NumberOfWays[Num]); //Change this for UVa - 357 - Let Me Count The Ways
}

No comments: