题目描述：
你有n种不同面值的硬币，每种面值的硬币都有无限多个，为了方便购物，你希望带尽量少的硬币，并且要能组合出 1 到 m 之间（包含1和m）的所有面值。
输入描述：
第一行包含两个整数：m ，n（1 ≤ n ≤ 100，1 ≤ m ≤ 10），意义如题目描述。接下来的 n 行，每行一个整数，第 i + 1 行的整数表示第 i 种硬币的面值。
输出描述：
输出一个整数，表示最少需要携带的硬币数量，再输出以空格为分隔的一串整数，表示对应的硬币面值。如果无解，则输出-1。
示例：
输入：
20 4
1
2
5
10
输出：
5
1 2 2 5 10
分析：
首先，硬币面值必须有1，否则无法组合1（其实只要有了1，便可以组合出任意面值）。
用sum表示当前能组合的最大面值，即可以组合1~sum的所有面值。
当sum ≥ m时，就停止组合。
当sum ＜ m时，要继续组合，即组合sum + 1，我们事先把不同面值的硬币排序，从这里面找到满足 ≤ sum + 1的最大面值的硬币，为什么需要是最大面值呢，因为这样才能保证硬币数最少。假设找到的硬币面值是coin[i]，此时，更新sum += a[i]，并将硬币数量+1。以上面的示例为例，当sum = 4时，下一次要凑5，我们在面值数组里找到了满足条件的5，因为sum = 4表示能凑齐1~4，现在有了面值为5的硬币，又可以组合出5~9，总共可以组合出1~9，所以我们更新sum = 4 + 5 = 9，表示现在可以组合1~9。按此思想，如此循环下去……，直到sum ≥ m。
显然是用贪心算法来解决问题了。
代码：
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std; int main()
{
int m = ; // 要组合出1~m的任意面值
int n = ; // 不同面值的硬币数量
vector<int> coin; // 不同面值的硬币
int sum = ; // 当前能组合出的最大面值
int count = ; // 当前需要的硬币数量
vector<int> trace; // 当前需要的硬币面值
cin >> m >> n;
for (int i = ; i < n; i++){
int temp;
cin >> temp;
coin.push_back(temp);
}
sort(coin.begin(), coin.end()); //硬币按面值升序排列
// 如果没有面值为1的硬币，则无解
if (coin[] != ){
cout << - << endl;
system("pause");
return ;
}
while (true){
// 如果可以组合出大于等于m的面值，则输出count
if (sum >= m){
cout << count << endl;
for (auto &i : trace)
cout << i << "\t";
system("pause");
return ;
}
// 找满足<= sum + 1的最大面值的硬币
for (int i = n - ; i >= ; i--){
if (coin[i] <= sum + ){
trace.push_back(coin[i]); // 保存需要的硬币面值
sum += coin[i]; // 更新sum
count++; // 更新count
break; // 跳出并判断此时的sum是否>=m
}
}
}
return ;
}
测试：