You have given solution for number of coins required for different sum as explained on topcoder tutorial. But I think the question has put forward some conditions based on which it asks us to find the denominations of the 6 coins. You have taken the sum given(which cannot be obtained by using coins we have) in the problem as denominations.
I think you have interpreted it erongly. Just hope my interpretation is correct :) On Tue, Jul 5, 2011 at 5:25 PM, Azhar Hussain <[email protected]> wrote: > What I understood from the statement is what is the 'minimum denomination' > required for a given value. > > I will try to explain it in short > we can solve the problem as sub-problems > > Lets say you want a denomination for some sum S and 'i' be the previous sum > so i <= S. > If we can find the sum at i we can find the sum for i+1 using i as our > reference. > > For example S= 15. What is the minimum denomination required using the > coins 5, 10 > from the statement above I cannot calculate sums other than multiples of 5. > So, I will write down sums which are multiples of 5 upto 15. > 0 > 5 > 10 > 15 > > Inorder to calculate denominations for 15. I must have calculate > denominations of 15, 5, 0 > > Goal: > First 0, this does not require coins so coins are 0. > Sum 5, we have found the solution yet for this mark it as infinity. We see > that there is only one coin in the denomination pool which is less than this > sum. > Sum 10, If I can take the previous sum 10 - 5, I will end up having 2 coins > but the best solution would be denomination of 10 i.e., 1 coin. I compare > the denominations value and the previous sum and store the minimum value. > Sum 15, From the previous step 1 coin for 10 and 5 denomination will make > up the sum so number of coins are 2. > > this can be recursively defined as > if ((N[j] <= i) && ((Min[i-N[j]] + 1) < Min[i])) > Min[i] = Min[i-N[j]] + 1; > > Where N is the denominations > i is the Previous Sum denoted as Min > j is the index of denomination > > sum[1,, 15] = infinity; > for sum 0 i = 0; N[0] = 5 and 5 <= is false sum remains 0, so Sum[0] = 0. > for Sum 5 i = 5 ; N[0] = 5 and 5 <= 5 true and (Sum[5-5] + 1) < Sum[5] > update the sum[5] = sum[5-5] + 1; > //// + 1 because including N[j] coin makes the sum > do the same for remaining sums. > > > can be represented mathematically like this > *C*(*N*,*m*) = *C*(*N*,*m* - 1) + *C*(*N* - *S**m*,*m*) > > Or This is the least I can say. > M(j) = Minimum number of coins required to make change for amount of money > j. > M(j) = Min { M( j - vi ) } + 1; > i > complexity O(n^S) for the Sum S. > > - > Azhar. > > > > - > Azhar. > > > > > On Tue, Jul 5, 2011 at 4:37 PM, Dumanshu <[email protected]> wrote: > >> @Azhar: could u plz explain the q8. problem. >> >> On Jul 5, 12:13 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 athttp:// >> 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. > -- Tushar Bindal Computer Engineering Delhi College of Engineering Mob: +919818442705 E-Mail : [email protected] Website: www.jugadengg.com -- 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.
