找零钱问题的动态规划和贪心算法对比

动态规划算法一定是最优解，而贪心未必

如果是中国的零钱，1,2,5,10,50,100 贪心即可得到最优解

但如果序列不是1 2 5 10 ,或着类似的问题，则需要小心使用贪心算法

算法思路

动态规划:

• k元找零 等效于 k-1,k-2,k-5,k-10找零里面最小的 再加一

贪心算法:

• 优先使用较大的金额

遍历10以内的所有递增序列,分析贪心和动态规划答案相同与不相同的序列规律

money = [1,1,1] 
for a in range(1,9):
    money[0] = a
    for b in range(a+1,10):
        money[1] = b
        for c in range(b+1,11):
            money[2] = c
            flag = True # 记录两种算法结果是否相同
            target = 1
            while target < 100:

                # 动态规划解法
                l = [0] * (target+1) # l[0] 需初始化为0
                for k in range(1,target+1):
                    min = target
                    for m in money:
                        if m<=k:
                            if min>l[k-m]:
                                min = l[k-m]
                        else:
                            break
                    l[k] = min + 1


                # 贪心算法解法 先用最大面额的
                sum = 0
                c_target = target
                sum +=c_target//money[2]
                c_target %= money[2]
                sum +=c_target//money[1]
                c_target %= money[1]
                sum +=c_target
                if sum != l[target]:
                    flag = False
                    # print(money) #输出not equal list
                    break
                target += 1
            if flag:
                print(money) #输出equal list

结果分析

两种解法结果一致的money取值

规律：前面的数乘2不大于后面的数+1 (必要条件) m1|m2|m3 :-:|:-:|:-: 1 | 2 | 3 1 | 2 | 4 1 | 2 | 5 1 | 2 | 6 1 | 2 | 7 1 | 2 | 8 1 | 2 | 9 1 | 2 | 10 1 | 3 | 5 1 | 3 | 6 1 | 3 | 7 1 | 3 | 8 1 | 3 | 9 1 | 3 | 10 1 | 4 | 7 1 | 4 | 8 1 | 4 | 10 1 | 5 | 9 1 | 5 | 10

两种解法结果不一致

证明上述规律不是充分条件

当money = 【1 | 4 | 9】时 target=16 |动态规划:4*4. 贪心:9+4+1+1+1