Bytelandian Gold Coin,动态编程,解释?

这有点不成熟,但我不得不问,

这里提到的Bytelandian金币问题 – http://www.codechef.com/problems/COINS/ ,据说是典型的DP问题,尽管我已经阅读了DP和递归的基础知识,但我发现很难理解它解,

# include  # include  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; return current; } long unsigned int findOptimalAmount(short int factor2,short int factor3) { unsigned int n = currentValue(factor2,factor3); if(n < 12) { costArray[factor2][factor3] = n; return (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)); return 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)); } return 0; } 

就像它的递归是如何工作的一样? costArray的大小如何确定为30×19?

另外,我如何才能提高解决问题的思路?

谢谢!

你的解释是正确的。 但这里重要的一点仍然无法解释。 这是f(n)定义的内容

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

最大的是f(n)的解。 进一步挖掘,对于所有n <12 f(n)都大于f(n / 2)+ f(n / 3)+ f(n / 4)。 这将成为递归的停止条件。 虽然起初上面的表达看起来似乎是一个微不足道的递归,但它的实现会导致效率非常低效(因为没有被spoj接受)。

我们必须有一些如何存储函数f的中间值,使得递归实现的一部分将成为存储值的查找。

不幸的是,直接存储像fibbonaci系列的memoziation这样的值对于这个例子是行不通的。 因为在给定的程序中,n可以达到1000000000而且我们不能创建一个大小为1000000000的数组。所以这里有一个聪明的技巧,而不是直接为每个n存储子问题的值。 我们知道n在每个阶段被细分2(最多30次)和3(最多20次)(除以4只是除以2两次),所以我们将考虑一个大小为30×20的矩阵,其中索引为i的元素,j表示当用i乘2和j乘3时n的值。这样给定问题f(n)变换为F(0,0)。 现在我们在F上应用递归,并在每个阶段使用n值的memoization。

 #include #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 by nthDiv2 and nthDiv3 */ unsigned long long current(int nthDiv2, int nthDiv3) { int i = 0; unsigned long long nAfterDiv2 = n >> nthDiv2; unsigned long long nAfterDiv2Div3 = nAfterDiv2; for (i = 0; i < nthDiv3; i++) nAfterDiv2Div3 /= 3; return nAfterDiv2Div3; } unsigned long long F(int nthDiv2, int nthDiv3) { /* if the value of n when divided by nthDiv2 and nthDiv3 is already calculated just return it from table */ if (ff[nthDiv2][nthDiv3] != 0) return ff[nthDiv2][nthDiv3]; else { //calculate the current value of n when divided by nthDiv2 and nthDiv3 => F(nthDiv2, nthDiv3) unsigned long long k1 = current(nthDiv2, nthDiv3); if (k1 < 12) /* terminating condition */ return k1; unsigned long long t = F(nthDiv2 + 1, nthDiv3) + F(nthDiv2, nthDiv3 + 1) + F(nthDiv2 + 2, nthDiv3); /* Maximum of F(nthDiv2, nthDiv3) and F(nthDiv2 + 1, nthDiv3) + F(nthDiv2, nthDiv3 + 1) + F(nthDiv2 + 2, nthDiv3) */ return ff[nthDiv2][nthDiv3] = max2(k1 , t); } } int main() { int i, j; while (scanf("%llu", &n) != EOF) { /* Every testcase need new Memoization table */ for (i = 0; i < 30; i++) for (j = 0; j < 20; j++) ff[i][j] = 0; printf("%llu\n", F(0, 0)); } return 0; } 

在此处输入图像描述

谢谢大家的评论!

根据我的理解回答它,

这个,

 costArray[factor2][factor3] = (findOptimalAmount(factor2+1,factor3) + findOptimalAmount(factor2,factor3+1) + findOptimalAmount(factor2+2,factor3)); 

只是一种奇特的推杆方式,

 cost = optimalAmount(n/2) + optimalAmount(n/3) + optimalAmount(n/4); 

递归地,直到基本条件 – amount < 12 ,并且值存储在一个数组中( 30x20 ,最大因子可能为1000000000 ~ 2^30 ~ 3^20 ,感谢Pavel&Picarus),并且所有都添加到得到最终价值。

plus num>>1num/2num>>2num/4 ,依此类推(在currentValue() )。

新手的解释,欢迎您编辑!

猜猜我只需要练习更多。

这是我使用c#解决这个问题的版本:

 class MainBytelandian { //Temp Global variables private static List FinalCollectionofCoins = new List(); static void Main() { string TempEntry = string.Empty; int TempNumber; Console.WriteLine("Welcome to Bytelandian gold coins program"); // Welcome message Console.WriteLine("Please provide your Bytelandian gold coin"); // Input int.TryParse(TempEntry = Console.ReadLine(), out TempNumber); ExchangeGoldCoins(TempNumber); Console.WriteLine("{0}", FinalCollectionofCoins.Sum()); Console.Read(); }//End of main() static void ExchangeGoldCoins(int GoldCoin) { int SumOfExchangedCoins = (GoldCoin / 2) + (GoldCoin / 3) + (GoldCoin / 4); if (SumOfExchangedCoins > GoldCoin) { ExchangeGoldCoins(GoldCoin / 2); ExchangeGoldCoins(GoldCoin / 3); ExchangeGoldCoins(GoldCoin / 4); } else //If it's not more add its value to the final collection and return empty list { FinalCollectionofCoins.Add(GoldCoin); } } }