题目描述:

你有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 ;
}

测试:

最少的硬币数量组合出1到m之间的任意面值(贪心算法)-LMLPHP

最少的硬币数量组合出1到m之间的任意面值(贪心算法)-LMLPHP

05-11 13:55