c语言 贪心算法 找零钱

以下是使用贪心算法找零钱的C语言代码示例：

#include <stdio.h>

void findChange(int money, int a, int b, int c) {
    int sum, i = 0, m = 0, n = 0;
    while (1) {
        sum = a * n + b * m + c * i; // 总钱数求解
        if (sum == money) { // 满足条件结束循环
            printf("a:%d, b:%d, c:%d\n", n, m, i); // 打印输出i，m，n的数值
            break;
        }
        if (sum > money) { // 总钱数超过money，需要回退
            if (m > 0) { // 尝试减少b的个数
                m--;
                n = (money - c * i - b * m) / a;
            } else if (i > 0) { // 尝试减少c的个数
                i--;
                m = (money - c * i) / b;
                n = (money - c * i - b * m) / a;
            } else { // 无法回退，退出循环
                break;
            }
        } else { // 总钱数小于money，增加a的个数
            n++;
        }
    }
}

int main() {
    int money = 15, a = 5, b = 2, c = 1;
    findChange(money, a, b, c);
    return 0;
}

该算法的思路是从大面值开始，尽可能多地使用大面值，直到总钱数超过money，然后回退到上一个状态，尝试减少大面值的个数，增加小面值的个数，直到找到最优解或者无法回退为止。