【数据结构与算法】贪心算法

2024/10/24 19:16:08 来源：https://blog.csdn.net/qq_74047911/article/details/141285602 浏览: 次关键词：【数据结构与算法】贪心算法

贪心算法目录

一.贪心算法的思路
二.换零钱
三.完整代码
四.贪婪使用场景

一.贪心算法的思路

贪心顾名思义,比如说现在我贪玩,不卷,那么我以后可能会不爽,但是现在我非常爽,就是当下的最有解.
就是我看眼前的我怎么舒服怎么来.

二.换零钱

一般我们会设置手头面值最大的值来进行换取,不够再用小面值的凑.
假设如下是我所拥有的零钱value是面值,count是对应面值的数量.
在这里插入图片描述
那么我是从后往前来进行的遍历先是面值最大的.

在这里插入图片描述
可以自动需要几张.

判断该面值的数量够不够.

三.完整代码

#include <stdio.h>
#include <stdlib.h>#define N 7int value[N] = { 1,2,5,10,20,50,100 };
int count[N] = { 10,2,3,1,2,3,5 };//int value[N] = { 1,2,5,10,20,50,100 };//不是最优解
//int count[N] = { 0,0,0,0,3,1,0 };int solve(int money)
{int num = 0;int i = 0;for (i = N - 1; i >= 0; i--){int j = money / value[i];int c = j > count[i] ? count[i] : j;printf("需要用面值 %d 的纸币 %d z张\n", value[i], c);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;printf("请输入要换的钱数目:\n");scanf_s("%d", &money);num = solve(money);if (num == -1){printf("对不起,找不开\n");}else{printf("成功的使用至少%d张纸币实现找零\n", num);}system("pause");return 0;
}