Change Making (Dynamic Programming) Problem

This is a classic change making problem.
A variant of the same problem, counting the number of ways to make the change is here

Problem Name : Making Change
Problem ID   : 2768
Problem URL  : http://acm.tju.edu.cn/toj/showp2768.html
Solution     :

 1# include <iostream>
 2# include <cstdio>
 3# include <cstring>
 4# include <algorithm>
 5int denoms [10];
 6int change [1001];
 7using namespace std;
 8int main()
 9{
10 //freopen ("Input.txt", "r", stdin);
11 //freopen ("Scratch.txt", "w", stdout);
12 int C, N;
13 scanf ("%d%d", &C, &N);
14 fill (change, change + C + 1, 10000);
15 for (int i = 0; i < N; i++) scanf ("%d", &denoms[i]);
16 sort (denoms, denoms + N);
17 change[0] = 0;
18 for (int j = 0; j < N; j++)
19  for (int i = denoms[j]; i <= C; i++)
20   change[i] = min (change[i], change[i - denoms[j]] + 1);
21 printf ("%d\n", change[C]);
22}