This is a classic change making problem.
A variant of the same problem, counting the number of ways to make the change is here
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 :
# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
int denoms [10];
int change [1001];
using namespace std;
int main()
{
//freopen ("Input.txt", "r", stdin);
//freopen ("Scratch.txt", "w", stdout);
int C, N;
scanf ("%d%d", &C, &N);
fill (change, change + C + 1, 10000);
for (int i = 0; i < N; i++) scanf ("%d", &denoms[i]);
sort (denoms, denoms + N);
change[0] = 0;
for (int j = 0; j < N; j++)
for (int i = denoms[j]; i <= C; i++)
change[i] = min (change[i], change[i - denoms[j]] + 1);
printf ("%d\n", change[C]);
}