Q8 is a DP problem, here is the solution
#include <stdio.h>
#define MAX 125
#define VAL 6
int Min[MAX];
int N[VAL] = {5, 10, 20, 25, 50, 100};
int main(void)
{
int i, j;
for (i = 1; i < MAX; i++)
Min[i] = 1000000;
for (i = 5; i < MAX; i += 5)
for (j = 0; j < VAL; j++)
if ((N[j] <= i) && ((Min[i-N[j]] + 1) < Min[i]))
Min[i] = Min[i-N[j]] + 1;
fprintf(stderr, "\n***\n");
for (i = 0; i < MAX; i += 5)
fprintf(stderr, "%d = %d\n", i, Min[i]);
return 0;
}
OUTPUT:
***
0 = 0
5 = 1
10 = 1
15 = 2
20 = 1
25 = 1
30 = 2
35 = 2
40 = 2
45 = 2
50 = 1
55 = 2
60 = 2
65 = 3
70 = 2
75 = 2
80 = 3
85 = 3
90 = 3
95 = 3
100 = 1
105 = 2
110 = 2
115 = 3
120 = 2
more information can be found at
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg
-
Azhar.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
