动态编程 - 硬币更改决策

Question

我正在审查算法课程中的一些旧笔记,动态编程问题对我来说似乎有点棘手.我有一个问题,我们有无限量的硬币,有一些面额x1,x2,... xn我们想要改变一些价值X.我们正在设计一个动态程序来决定是否可以改变X是否制造(不是最小化硬币数量,或返回哪些硬币,只是真或假).

我已经做了一些关于这个问题的思考,我可以看到这样做的递归方法,就像它...

MakeChange(X, x[1..n this is the coins])
    for (int i = 1; i < n; i++)
    {
        if ( (X - x[i] ==0) || MakeChange(X - x[i]) )
            return true;
    }
    return false;

转换这个动态程序对我来说并不容易.我怎么能接近这个？

Answer 1

您的代码是一个良好的开端.将递归解决方案转换为动态编程解决方案的常用方法是"自下而上"而不是"自上而下".也就是说,如果您的递归解决方案使用较小x的值计算特定X的某些内容,则从较小的x 开始计算相同的内容,并将其放在表中.

在您的情况下,将MakeChange递归函数更改为canMakeChange表.

canMakeChange[0] = True
for X = 1 to (your max value):
   canMakeChange[X] = False
   for i=1 to n:
     if X>=x[i] and canMakeChange[X-x[i]]==True: 
       canMakeChange[X]=True