有 n 种不同面值的硬币，每种硬币有无限多个。为了方便购物，他希望带尽量 少的硬币，但是要能组合出 1 到 m 之间的任意值。 //第一行为两个整数：m 和 n，他们的意义如题目描述。接下来的 n 行

题目：有 n 种不同面值的硬币，每种硬币有无限多个。为了方便购物，他希望带尽量 少的硬币，但是要能组合出 1 到 m 之间的任意值。第一行为两个整数：m 和 n，他们的意义如题目描述。接下来的 n 行，每行一个整数，第 i + 1 行的整数表示第 i 种硬币的面值最少需要携带的硬币数量，如果无解则输出-1。

输入：
20 4
1 2 5 10
输出：
5

分析：sum表示当前能凑到的最大面值(即1~sum的面值都凑到了)，当sum超过m,就停止(m是题上要求凑1~m的面值)a[i]里存的是不同的面值将面值数组排序后，没有面值是1的必然无解，而且面值1必选。对于1~m,凑的时候先凑小的，因为小的多了可以满足大的。此外还有一个思想就是如果当前1~sum面值凑够了,那么下一步应该考虑凑sum+1的面值，具体过程是在排好序的面值数组中，从大到小找，找一个元素a[i](面值<=sum+1的)加等到sum上，这意味着1~(sum+a[i])面值凑齐了，这里找面值<=sum+1的寓意是保证能够凑齐的面值从sum+1面值开始到sum+a[i]面值是连续的。(例如某个时刻sum等于5,那么说明下一个要凑的面值是6，此时我们在面值数组中从大->小找<=6的元素(面值1,2,5,10)，我们找到了5，那么由于sum等于5，说明1~5的面值已经凑齐了，此时如果再添加一个面值是5的硬币，那么我们是不是就可以凑齐1~10了，这里不仅凑齐了6，还多凑齐了7,8,9,10，但是要是取一个大于6的比如是10，那么1~5凑齐了ÿ

最后

以上就是孤独曲奇为你收集整理的有 n 种不同面值的硬币，每种硬币有无限多个。为了方便购物，他希望带尽量 少的硬币，但是要能组合出 1 到 m 之间的任意值。 //第一行为两个整数：m 和 n，他们的意义如题目描述。接下来的 n 行的全部内容，希望文章能够帮你解决有 n 种不同面值的硬币，每种硬币有无限多个。为了方便购物，他希望带尽量 少的硬币，但是要能组合出 1 到 m 之间的任意值。 //第一行为两个整数：m 和 n，他们的意义如题目描述。接下来的 n 行所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。