问题描述
小Q去商场购物，经常会遇到找零的问题。
小Q现在手上有n种不同面值的硬币，每种面值的硬币都有无限多个。
为了方便购物，小Q希望带尽量少的硬币，并且要能组合出1到m之间（包含1和m）的面值。
输入描述
第一行包含两个整数m，n
接下来的n行表示n种硬币的面值
输出格式
最少需要携带的硬币数量，如果无解则输出-1
样例输入
20 4
1
2
5
10
输出
5
数据范围
1<=m<=10^9，1<=n<=100
一开始真的不会做，后来看了大佬们的思路才知道如何解，记录一下这个题。
分析如下
看似背包，其实是贪心：从1逐渐满足到m的策略。
假设现在硬币 res = [1,2] 表示当前使用了一个1面值的硬币，一个2面值的硬币，在这种情况下，你能表示区间 sum= 3 以内的所有数据（线性组合）。此时考虑再加一枚什么面值的硬币最优，使他之后的区间满足。之后的区间为：[当前能满足区间的最大值, 候选硬币值）, 也就是[3, 5), 当前的硬币组合是不能满足这个区间要求的（4这个元素满足不了）。因此我们应该贪心的加上一个当前面值最大的硬币，也就是面值为2的硬币，也就是说 res = [1,2,2] , 此时的线形组合能满足的最大区间为 sum = 3+2 = 5 , 也就是说可以满足了,以此类推往下继续走.
代码:
#coding=utf-8
import sys
if __name__ == "__main__":
lines = sys.stdin.readlines()
m, n = list(map(int, lines[0].strip().split()))
coins = []
for line in lines[1:]:
coins.append(int(line.strip()))
su = coins[0]
res = [coins[0]]
i = 1
while(i<n):
if su >= (coins[i] - 1):
i += 1
else:
res.append(coins[i-1])
su += res[-1]
while(su<m):
res.append(coins[-1])
su += res[-1]
print len(res)
总结
其实是一道区间贪心的题目，还是经受的毒打太少了。
WechatIMG94.jpeg
(循环处的贪心思想代码还可以再精简，直接统计个数，不需要开辟res数组空间，只是为了调试）
