c - Bytelandian Gold Coin , Dynamic programming , explanation? -

c - Bytelandian Gold Coin , Dynamic programming , explanation? -

it's bit immature, have ask,

the bytelandian gold coin problem mentioned here - http://www.codechef.com/problems/coins/ , said typical dp problem,even though have read basics of dp & recursion, finding hard understand solution,

# include <stdio.h> # include <stdlib.h> long unsigned int costarray[30][19]; unsigned int amount; unsigned int currentvalue(short int factor2,short int factor3) { int j; unsigned int current = amount >> factor2; for(j=0;j<factor3;j++) current /= 3; homecoming current; } long unsigned int findoptimalamount(short int factor2,short int factor3) { unsigned int n = currentvalue(factor2,factor3); if(n < 12) { costarray[factor2][factor3] = n; homecoming (long unsigned int)n; } else { if(costarray[factor2][factor3] == 0) costarray[factor2][factor3] = (findoptimalamount(factor2+1,factor3) + findoptimalamount(factor2,factor3+1) + findoptimalamount(factor2+2,factor3)); homecoming costarray[factor2][factor3]; } } int main() { int i,j; while(scanf("%d",&amount) != eof) { for(i=0;i<30;i++) for(j=0;j<19;j++) costarray[i][j] = 0; printf("%lu\n",findoptimalamount(0,0)); } homecoming 0; }

like how recursion works? how costarray size decided 30x19?

also how can improve thinking such problems solving?

thanks!

your explanation correct. of import point here still unexplained. here f(n) defined be

max{ f(n) , f(n/2) + f(n/3) + f(n/4) }

whichever maximum solution f(n). digging little further, n < 12 f(n) greater f(n/2) + f(n/3) + f(n/4). become stopping status recursion. though @ first above look may seem trivial recursion, implementation lead inefficient algorithm(reason not getting accepted on spoj).

we have how store intermediate values of function f such way part of recursive implementation become lookup of stored values.

unfortunately straight storage of values memoziation of fibbonaci series not work example. because in given programme n can reach 1000000000 , can not create array of size 1000000000. here clever trick, instead of storing value of subproblem straight every n. know n subdivided 2(max 30 times) , 3(max 20 times) @ every stage(division 4 partition 2 twice), consider matrix of size 30x20 element @ index i,j denote value of n when divided times 2 , j times 3. way given problem f(n) transforms f(0,0). apply recursion on f , utilize memoization of value of n @ every stage.

#include<stdio.h> #define max2(a, b) ((a) > (b) ? (a) : (b)) unsigned long long ff[30][20] = {0}; unsigned long long n = 0; /* returns value of n when divided nthdiv2 , nthdiv3 */ unsigned long long current(int nthdiv2, int nthdiv3) { int = 0; unsigned long long nafterdiv2 = n >> nthdiv2; unsigned long long nafterdiv2div3 = nafterdiv2; (i = 0; < nthdiv3; i++) nafterdiv2div3 /= 3; homecoming nafterdiv2div3; } unsigned long long f(int nthdiv2, int nthdiv3) { /* if value of n when divided nthdiv2 , nthdiv3 calculated homecoming table */ if (ff[nthdiv2][nthdiv3] != 0) homecoming ff[nthdiv2][nthdiv3]; else { //calculate current value of n when divided nthdiv2 , nthdiv3 => f(nthdiv2, nthdiv3) unsigned long long k1 = current(nthdiv2, nthdiv3); if (k1 < 12) /* terminating status */ homecoming k1; unsigned long long t = f(nthdiv2 + 1, nthdiv3) + f(nthdiv2, nthdiv3 + 1) + f(nthdiv2 + 2, nthdiv3); /* maximum of f(nthdiv2, nthdiv3) , f(nthdiv2 + 1, nthdiv3) + f(nthdiv2, nthdiv3 + 1) + f(nthdiv2 + 2, nthdiv3) */ homecoming ff[nthdiv2][nthdiv3] = max2(k1 , t); } } int main() { int i, j; while (scanf("%llu", &n) != eof) { /* every testcase need new memoization table */ (i = 0; < 30; i++) (j = 0; j < 20; j++) ff[i][j] = 0; printf("%llu\n", f(0, 0)); } homecoming 0; }

c algorithm recursion dynamic-programming