程序员的数学之动态规划下

发表于 | 分类于 | 阅读次数:
字数统计: 354 | 阅读时长 ≈ 1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

import copy


def min_coins_recruit(target_money, coins):
    """
    对于总金额固定，使用函数的递归(嵌套调用)，找出最少钱币数
    :param target_money: 总金额大小
    :param coins: 可选面额的钱币列表，如 [2, 3, 7]
    :return:
    """
    if target_money == 0:
        return 0
    elif target_money < min(coins):
        return None  # 不存在或无解
    elif target_money in coins:
        return 1

    result = list()
    for j in coins:
        count = min_coins_recruit(target_money - j, coins)
        if count is None:
            continue
        else:
            result.append(count)
    if len(result) > 0:
        return min(result) + 1
    else:
        return None  # 不存在或无解


def min_coins_dyna_pro(target_money, coins):
    """
    对于总金额固定，使用动态规划算法，找出最少钱币数
    :param target_money: 总金额大小
    :param coins: 可选面额的钱币列表
    :return:
    """
    if min(coins) > target_money:
        return None
    # 每个额度的钱币数，初始化值为 None，假设不存在或无解
    count = list([None]*(target_money+1))
    # 一些确定额度的钱币数
    count[0] = 0
    for j in coins:
        if j <= target_money:
            count[j] = 1
    # 动态规划求解钱币数
    for i in range(min(coins) + 1, target_money+1):
        tmp_count = list()  # 临时保存钱币数
        tmp_coins = [j for j in coins if j <= i]  # 求解 count[i-j] 时，i-j 大于 0
        for j in tmp_coins:
            if count[i-j] is not None:
                tmp_count.append(count[i-j])
        if len(tmp_count) > 0:
            count[i] = min(tmp_count) + 1

    return count[target_money]


# 如何获取钱币组合？
if __name__ == "__main__":
    print("动态规划，最少钱币数：", min_coins_dyna_pro(50, [2, 3, 7]))
    print("递归方法，最少钱币数：", min_coins_recruit(50, [2, 3, 7]))