贪心算法-实现贪心算法的局限性
贪心算法的基本原理
贪心算法是使所做的选择看起来都是当前最佳的，期望通过所做的局部最优选择来产生出一个全局最优解 。
贪心算法的性质 贪心选择：在做贪心选择时，应满足可行性，即必须满足问题的约束条件 。局部最优：通过做一系列的选择来给出某一问题的最优解 。对算法中的每一个决策点，做一个当时最佳的选择 。子结构结果：贪心算法所做的当前选择可能要依赖于已经做出的所有选择，但不依赖于有待于做出的选择或子问题的解 。例题 找零钱问题
题目：假设有7种硬币，面值分别为0.01元、0.02元、 0.05元、 0.1元、 0.2元、 0.5元、 1元 。要找6.66元，问如何找钱才能使找出的硬币个数最少？
核心思想：每一次找钱都从零钱面值最大的算起，以确保每次找出的硬币数目最少
基本思路：
读取硬币和零钱的数值从面值最大的硬币开始找起，逐步递减直到零钱值为零
代码如下：
%贪心算法解决找零钱问题% greedy algorithm(GA)贪心/贪婪算法d=[0.01 0.02 0.05 0.5 0.1 0.2 1]%输入零钱面值，存入d数组中%将数组d排序，使得其零钱面值为从小到大value=http://www.kingceram.com/post/sort(d)a= input('请输入需要找的零钱数:')%a表示需要找的零钱数i=length(value)%用length函数计算d数组的长度while i>0if a>=value(i) %从面值最大的开始找,d[i]此时i=6 i的值是最大的，d[i]是最大的n=fix(a/value(i))%fix函数用于向下取整，n的含义是需要找的零钱个数a=round(a-n*value(i),2)%round保留两位小数X=sprintf('找了%d个%.2f元硬币',n,value(i))disp(X)endi=i-1end
空瓶换酒问题
题目：小区便利店正在促销，用 3 个空酒瓶可以兑换一瓶新酒 。你购入了 5 瓶酒 。如果喝掉了酒瓶中的酒，那么酒瓶就会变成空的 。请你计算最多能喝到多少瓶酒？
核心思想：每一次换酒都尽最大可能换最多的酒
基本思路：
设置交换规则并读取初值记录剩余酒瓶的数量、喝到的酒的数量，当剩余酒瓶已经不能换酒时，停止循环
文章插图
空瓶换酒问题示意图如下：
代码如下：
%贪心算法解决空瓶换酒问题% greedy algorithm(GA)贪心/贪婪算法a=1while a==1%购入了 n 瓶酒n = input('你现在有几瓶酒？');%用 m 个空酒瓶可以兑换一瓶新酒m = input('几个酒瓶可以换一瓶酒？');if m<=1disp('输入错误 请重新输入')a=1else a=0endend%初始化count = n;% 喝到酒的数目e = n;% 空瓶数目%初始时，空瓶数量等于已有酒的数量，还未开始换酒while fix(e / m) ~= 0 %fix函数向下取整，当手里有的空瓶数量一瓶酒的换不了了就结束循环bottle = fix(e / m);% 利用当前空瓶最大限度地兑换酒，得到当前酒的数目count = count + bottle;% 更新喝到酒的数目e = mod(e,m) + bottle; %更新空瓶数目:空瓶=兑换后剩余空瓶+兑换得到的酒瓶mod函数：返回 e 除以 m 后的余数endX=sprintf('一共可以喝到%d瓶酒',count)disp(X)当酒的瓶盖也可以换酒时，则需考虑两个数量的变化，找到最大换酒数量，代码如下：
%贪心算法解决空瓶换酒问题2.0版% greedy algorithm(GA)贪心/贪婪算法%初始化clc;clear;n=20%共有n瓶酒m=2%用 m 个空酒瓶可以兑换一瓶新酒q=3%用q个瓶盖可以换1瓶酒count = n;% 喝到酒的数目e = n;% 空瓶数目f = n;%瓶盖数目while (fix(e / m) ~= 0 )||(fix(f/q)~=0)%fix函数向下取整，当手里有的空瓶数量一瓶酒的换不了了就结束循环if fix(e / m) ~= 0bottle_e = fix(e / m) % 利用当前空瓶最大限度地兑换酒，得到当前酒的数目endif fix(f / q) ~= 0bottle_f = fix(f / q)% 更新喝到酒的数ende = mod(e,m) + bottle_e+bottle_f; %更新空瓶数目:空瓶=兑换后剩余空瓶+兑换得到的酒瓶mod函数：返回 e 除以 m 后的余数f = mod(f,q) + bottle_f+bottle_e; %更新瓶盖数目:瓶盖=兑换后剩余瓶盖+兑换得到的瓶盖count = count + bottle_e+bottle_f;bottle_e=0bottle_f=0endX=sprintf('最终喝到%d瓶酒',count)%最终喝到酒的瓶数disp(X)
- 二进制算法教程,二进制算法
- 1 python - 算法类 毕设选题
- 算法分析与设计 练习三
- 贪心算法 用c语言实现田忌赛马
- c语言贪心算法 渊子赛马
- 问鼎CodeXGLUE榜单，华为云UniXcoder-VESO-v1算法取得突破
- 带图详解 【算法模板】高精度模板
- PLC算法系列之数值微分器
- 数据挖掘分类算法的学习总结
- 一 MATLAB智能算法实现