贪心算法——硬币找零2——python

找零钱问题（难度系数为3）

« 问题描述

设有n种不同面值的硬币，各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱，可以实用的各种面值的硬币个数不限。当只用硬币面值T[1],T[2],…,T[i]时，可找出钱数j的最少硬币个数记为C(i,j)。若只用这些硬币面值，找不出钱数j时，记C(i,j)=∞。

«编程任务

设计一个动态规划算法，对1≤j≤L，计算出所有的C( n,j )。算法中只允许实用一个长度为L的数组。用L和n作为变量来表示算法的计算时间复杂性

«数据输入

从屏幕输入数据。输入第1行中有1个正整数n（n<=13），表示有n种硬币可选。接下来的一行是每种硬币的面值。由用户输入待找钱数j。

« 结果输出

 程序运行结束时，将计算出的所需最少硬币个数输出到屏幕。

输入示例	输出文件示例
3 1 2 5 9	3

def get_min_coins(coin_combinations,amount_rem):
    coin_list = []
    
    sorted_coin_combinations = sorted(coin_combinations, reverse = True)   #将面值从大到小排序
    
    for coin_val in sorted_coin_combinations:
        coin_count = int(amount_rem/coin_val)     #计算每个面值的个数（换成零钱时）
        coin_list += [coin_val]*coin_count        #将零钱放入输出列表
        
        amount_rem -= coin_val * coin_count       #找零之后，剩下的钱
        if amount_rem <= 0:
            break
    if amount_rem != 0:
        print("无法找零！")
    else:
        return coin_list
        


if __name__ == "__main__":
    n = (int)(input("请输入面值个数："))
    coin_combinations = []
    for i in range(n):
        coin_combinations.append((int)(input("面值：")))
    money = (int)(input("需要找的零钱："))
    print(get_min_coins(coin_combinations,money))