Bytelandian金币，动态规划，解释？ [英] Bytelandian Gold Coin , Dynamic programming , explanation?

问题描述

这是一个有点稚嫩，但我要问，

It's a bit immature, but I have to ask,

这里提到的Bytelandian金币的问题 - HTTP：//www.$c$cchef .COM /问题/硬币/ ，
被认为是典型的DP问题，即使我已阅读DP和放大器的基本知识;递归，但我发现很难理解其解决方案，

The Bytelandian Gold coin problem mentioned here - http://www.codechef.com/problems/COINS/ , is said to be typical DP problem,even though I have read basics of DP & recursion, but I am finding hard to understand its 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;
    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？

Like how does its recursion works? How is costArray size is decided to be 30x19?

此外，我怎么能提高我解决这样问题的思考？

Also how can I improve my thinking for such problems solving?

谢谢！

推荐答案

你的解释是正确的。但这里重要的一点是仍然不明。这里是F（n）被定义为

your explanation is correct. But the important point here is still unexplained. Here is what f(n) is defined to be

{最大值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）。这将成为递归的停止条件。虽然起初上述前pression看似小事递归，它的实施将导致非常低效的算法（之所以没有得到公认的spoj）。

whichever is maximum is the solution for f(n). Digging little further, for all n < 12 f(n) is greater than f(n/2) + f(n/3) + f(n/4). This will become the stopping condition for the recursion. Though at first the above expression may seem a trivial recursion, Its implementation would lead to very inefficient algorithm(reason for not getting accepted on spoj).

我们有一些如何存储的函数的中间f的数值这样的方式递归实现的一部分将成为存储的值的查找。

We have to some how store the intermediate values of function f such a way that part of the recursive implementation would become lookup of the stored values.

像fibbonaci系列memoziation价值观不幸的是直的存储不会在这个例子中工作。因为在给定的程序n可达到10亿，我们不能创建大小为1000000000.的数组，因此，这里是巧招，而不是直接存储子问题的价值为每n。我们知道，n由2（最多30次）和3（最大20倍），在每一个阶段划分（4师就是通过2个师两次），所以我们会考虑在索引大小30x20的矩阵，其中的元素i ，J表示n值时以i次通过2和j倍除以3通过这种方式，给定的问题F（N）变换到F（0,0）。现在，我们运用F上的递归，并在每个阶段使用n值的记忆化。

Unfortunately straight storage of the values like memoziation of fibbonaci series would not work for this example. Because in the given program n can reach 1000000000 and we can not create an array of size 1000000000. So here is the clever trick, instead of storing the value of the subproblem directly for every n. We know that n is subdivided by 2(max 30 times) and 3(max 20 times) at every stage(division by 4 is just division by 2 twice), So we will consider a matrix of size 30x20 where an element at index i,j denote the value of n when divided with i times by 2 and j times by 3. This way the given problem f(n) transforms to F(0,0). Now we apply recursion on F and use memoization of the value of n at 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 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;
}

这篇关于Bytelandian金币，动态规划，解释？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！