首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >动态规划:兑换65美分硬币的最小数量

问动态规划:兑换65美分硬币的最小数量
EN

Stack Overflow用户
提问于 2014-10-29 21:41:57
回答 2查看 897关注 0票数 1

我试图用动态规划来解决一个问题,问题如下:

如果硬币(硬币、镍币、一角硬币、双一角硬币、四分之一硬币)的价值(1、5、10、20、25)是无限供应的,请找出最小数量的硬币来兑换65美分。使用了什么硬币(每个硬币多少枚)?说明使用动态规划算法所需的表格,以及如何获得所使用的硬币。

注:我不希望任何人为我演示整个表,但我有点拘泥于如何填写这个问题的表格。

我知道我的桌子看起来有点像这样:

代码语言:javascript
复制
    5   10  15  20  25  30  35  40  45  50  55  60  65
1

5

10

20

25

(我忽略了1,因为我知道这不是最好的解决方案)我最初的想法是,这张桌子会被填得有点像这样:

代码语言:javascript
复制
    5   10   15  20  25  30  35  40  45  50  55  60  65
1

5   1    2   4   5    5   6  7   8    9  10  11  12  13

10  0    1   

20

25

当我要走得更远的时候我就被困在这里了。我认为我并不完全理解动态编程是如何解决这个问题的。我一直在读我的书,并在网上阅读,但我仍然有点困惑。

编辑:

感谢其中一个答案,这就是我如何想出解决方案的方法:

代码语言:javascript
复制
    5     10    15    20    25    30    35    40    45    50    55    60    65
1   

5   1           1                  1                             1           

10         1    1                       1                              1     

20                    1                       2     1                        2

25                          1      1    1           1      2     2     2     1
EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2014-10-29 21:58:51

你做错了。列表示您必须返回的全部更改,行单元格表示所使用的某些硬币的数量(便士、镍、一角硬币、双一角硬币、四分之一硬币)。

该算法的全部目的是返回最小数量的硬币。例如,如果更改为25,您应该返回一个季度,而不是25美分。您可以看到,我在下面的表中使用了25美分列的四分之一。

在您的示例中,对于15项更改,您使用的是4x5美分,这是次优的,因为您可以使用一枚10美分的硬币和一枚5美分的硬币来返回总共15美分。在20美分栏中,您使用的是5x5美分的更改,这是不正确的,也不是最优的,因为您可以使用一枚20美分的硬币来返回20美分。

下面是为前5列填充的表。剩下的你可以补上:

代码语言:javascript
复制
    5   10   15  20  25  30  35  40  45  50  55  60  65
1

5   1        1     

10      1    1  

20               1

25                   1
--------------------------------------------------------
T   1   1    2   1   1

我已经在底部添加了一个T行,以计算您用作零钱的硬币总数。你的目标是拥有一个。行中每列的可能编号。

票数 1
EN

Stack Overflow用户

发布于 2014-10-29 22:16:53

仍然使用动态规划,我将把问题建模为构造一个图,其中节点是金钱的数量(节点N为N美分),其中有5种类型的有向边,{1,5,10,20,25},对应于硬币类型。

保持一个尚未找到最优解的节点的运行前沿。每次迭代时,边界上最小的节点必须是最优的,这样就可以删除它,将多达5个新节点加到边界上。

下面是用于算法的Python:

代码语言:javascript
复制
def change(coins, target):
    nodes = {0: (0, None)}
    frontier = set([0])
    while True:
        n = min(frontier)
        frontier.remove(n)
        if n == target:
            break
        elif n > target:
            return None # Infeasible!
        count = nodes[n][0]
        for coin in coins:
            m = n + coin
            frontier.add(m)
            if not m in nodes or nodes[m][0] > count + 1:
                nodes[m] = (count + 1, n)
    m = target
    sol = {}
    while True:
        n = nodes[m][1]
        if n is None:
            break
        coin = m - n
        sol[coin] = sol.get(coin, 0) + 1
        m = n
    return sol

print change([1, 5, 10, 20, 25], 65)

输出为{25: 1, 20: 2}。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/26641168

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档