比特兰金币，动态规划，解释？

Question

虽然有点幼稚，但我必须问一下：

在这里提到的Bytelandian Gold coin问题 - http://www.codechef.com/problems/COINS/， 被称为典型的DP问题，即使我已经了解了DP和递归的基础知识，但我仍然很难理解它的解决方案。

 # 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;
    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的大小是如何决定为30x19的？

此外，我如何提高解决这类问题的思维能力？

谢谢！

- amitfreeman

---

尝试绘制程序的流程图，或者只是 findOptimalAmount 函数。递归将变得非常明显。 - Felix Frank

正如Felix所说，有时绘制程序流程图可以展示系统的工作方式。通常在查看代码时，我们无法看到整体情况，因为我们被有限的机械细节所困扰。 - Happington

Factor2是初始金额被2整除的次数。Factor3是初始金额被3整除的次数。30和19分别是您的最大金额可以被2和3整除的最大次数。虽然这个问题实际上可以编码为动态规划，但我认为可能会有其他形式的递归更适合解决这个问题（个人意见）。正如其他同事所说，流程图将帮助您理解其余部分。 - Picarus

log3(1000000000) 的值约为 18.86。 - Pavel

Answer 1

您的解释是正确的。但这里仍然有一个重要的问题没有解释。下面是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的中间值，使递归实现的一部分变为查找存储的值。

不幸的是，直接存储值的方法(如斐波那契数列的记忆化)在这个例子中行不通。因为在给定的程序中，n可以达到1000000000，我们不能创建大小为1000000000的数组。所以这里有个聪明的技巧：不是直接存储每个n的子问题的值，而是我们知道在每个阶段n被2(max 30次)和3(max 20次)分割，所以我们将考虑一个大小为30x20的矩阵，在索引i,j处的元素表示n被2除以i次和3除以j次时的值。这样，给定问题f(n)转化为F(0,0)。现在我们对F应用递归，并在每个阶段使用n值的记忆化。

#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 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;
}

- Vineel

---

非常好的解决方案，非常感谢。对于像我这样需要简化版本的新手，我写了一个：https://ideone.com/RCH6xn - blz

Answer 2

这是我使用C#解决此问题的版本：

class MainBytelandian
    {
        //Temp Global variables
        private static List<int> FinalCollectionofCoins = new List<int>();

        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);
                     }


             }


        }

- IndieTech Solutions

Answer 3

感谢大家的评论！

为了我的理解，回答一下：

这个，

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），并全部相加以获得最终值。

此外，num>>1是num/2，num>>2是num/4等等（在currentValue()中）。

一个新手的解释，欢迎编辑！

我猜我只需要多练习。

- amitfreeman