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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.