硬币找零问题求解

问题描述

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

思路

数据量很大，动态规划不好做，也不好压缩，应该采用贪心的思路。首先如果没有面值为1的硬币必定无法满足要求可以直接输出-1，接下来考虑贪心策略，设想如果能够组合出1到5之间的任何数值，只要一个6的硬币就能组合出1到11的任意值，既如果当前能够组合出1到n的硬币，再加入一个n+1面值的银币就能组合出1到n+n+1的所有面值。所以基本思路就是用一个变量cur存储当前能表示的面值，将硬币排序，从大往小找到第一个小于等于cur+1的硬币，硬币数加一同时更新cur，当cur大于m时输出。

伪代码

sort(coin[])
while current_coin < m:
do
for n-1 to 0:
count++;
current = current_coin + coin[i];
break;
fi
done

code实现

#include <iostream>
#include <cmath>
#define
MAX_M 1000
#define
MAX_N 1000000000
void quickSort(int *a, int low, int high);
int main() {
int m, n;
std::cin >> m >> n;
int *coin = new int[n];
for (int i = 0; i < n; i++) {
std::cin >> coin[i];
}
quickSort(coin, 0, n - 1);//首先将数组排为非降序排序
int current_coin = 0;//当前总值
int count = 0;//硬币数目
while (current_coin < m) {
for (int i = n - 1; i >= 0; i--) {
if (coin[i] <= current_coin + 1) {
count++;
current_coin += coin[i];
break;
}
}
}
std::cout << std::endl;
std::cout << count << std::endl;
return 0;
}
void quickSort(int *a, int low, int high) {
if (low < high) {
int i = low;
int j = high;
int x = a[low];
while (i < j) {
while (i < j && a[j] >= x) {
j--;
}
if (i < j)
a[i++] = a[j];
while (i < j && a[i] < x)
i++;
if (i < j)
a[j--] = a[i];
}
a[i] = x;
quickSort(a, low, i - 1);
quickSort(a, i + 1, high);
}
}

最后

以上就是等待雪碧为你收集整理的贪心算法例子——硬币找零问题 硬币找零问题求解 的全部内容，希望文章能够帮你解决贪心算法例子——硬币找零问题 硬币找零问题求解 所遇到的程序开发问题。

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