C/C++ 数据结构五大核心算法之贪心算法_钱币找零问题

贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法。 贪婪算法所得到的结果往往不是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果。 贪婪算法并没有固定的算法解决框架，算法的关键是贪婪策略的选择，根据不同的问题选择不同的策略。 其基本的解题思路为： 1.建立数学模型来描述问题 2.把求解的问题分成若干个子问题 3.对每一子问题求解，得到子问题的局部最优解 4.把子问题对应的局部最优解合成原来整个问题的一个近似最优解。

#include <iostream>
#include <Windows.h>
#define N 7
using namespace std;
int value[N] = { 1,2,5,10,20,50,100 };//纸币面值
int count1[N] = { 10,2,3,1,2,3,5 };//纸币数量
int solve(int money) {
    int num = 0;
    for (int i = N - 1; i >= 0; i--) {
        int j = money / value[i];
        int c = j > count1[i] ? count1[i] : j;
        cout << "需要用面值" << value[i] << "的纸币" << c << "张" << endl;
        money -= c * value[i];
        num += c;
        if (money == 0)break;//零钱已经找完，直接退出程序
    }
    if (money > 0)num = -1;
    return num;
}
int main() {
    int money=0;
    int num = 0;
    cout << "请输入要支付的零钱数目：";
    cin >> money;
    num = solve(money);
    if (num == -1) {
        cout << "抱歉，找不开" << endl;
    }
    else {
        cout << "成功的使用至少" << num << "张纸币实现找零!" << endl;
    }

    system("pause");
    return 0;
}