问题 假设你当前拥有 3 元 6 元 7 元的硬币 数量为无限。问 假设你需要组合出 18 元,如何使硬币的数量最少 分析:我认为这个问题有点类似于 01 背包问题,很明显是不能用贪心算法来解决的,因为贪心的去首选最大的硬币是无法做到最优的,所以需要一个回溯寻找最优的机制来帮助我们解决问题,很显然,动态规划是首选。让我们看看他是否能用动态规划解决。

  • 最优子结构 假设需要组合 18 元,那么他其实完全可以基于一个比 18 小的数额 i 作为基础来进行硬币拼接,同时数额 i 仍然能够向下降低。所以他是拥有最优子结构的.

代码实现(python)

我们假设 d[i] 为当金额为 i 时,所需要的最小硬币数量,将 dg[i] 作为当金额为 i 时,所需要的最小硬币数量的组合方式。这是整个程序最核心的内容,并且将会保持不变,也就是循环不变式。在遍历硬币的过程中,去不断的尝试,能否找到使硬币的最小数量更小,直接的描述就是用于检测用一个 6 元的硬币能够抵消两个三元硬币,并且最小数量会降低,这就是回溯过程。举例:

但 i = 6 时 d[i - coin] + 1 等于 d[6 - 6] + 1 等于 d[0] 等于 1,这个 1 的意思就是 要凑六块钱,硬币数量最小为 1

def minNum(a, b):
    return a if a < b else b

# i 当前计算的金额 从0开始 不断增长 结束于和目标金额相等
# num 目标金额
# coins 硬币规格数组
def minCoins(i, num, coins):
    d = [0] * (num + 1)
    dg = [[]] * (num + 1)

    def _minCoins(i, num, coins):
        if(i == 0):
            d[i] = 0
            _minCoins(1, num, coins)
            return
        min = 9999
        for coin in coins:
            if(i >= coin):
                oMin = min
                min = minNum(d[i - coin]+1, min) # 代码的核心,不断的回溯,去尝试硬币更少的组合方式
                # 用于增加额外的信息 即组合方式
                if(oMin != min):
                    copy = dg[i - coin][:]
                    copy.append(coin)
                    dg[i] = copy
        d[i] = min
        if(i == num):
            return
        else:
            _minCoins(i+1, num, coins)

    _minCoins(i, num, coins)
    return d


# 硬币规格 无数量限制
coins = [3, 6, 7]

print(minCoins(0, 18, coins)[18])

最近在学python 感觉很有劲,简洁 语义化,不过字典没JS的对象字面量好用