don't give programs...... discuss the logic behind that, algorithms are important......
On Tue, Jul 5, 2011 at 12:43 PM, Azhar Hussain <[email protected]> wrote: > 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. > -- 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.
