|
|
马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有帐号？免费注册
x
本帖最后由 navebayes 于 2023-12-16 18:01 编辑
今天，小明在街上看见一个在街上叹气的老头儿，老头儿为什么叹气的呢？因为老头儿他今儿有些犟犟的；
地上不是有排砖儿嘛，这路年久失修了砖儿碎得这一块那一块的。老头儿散着步呢，心血来潮想到着
老汉儿我心情好，看着碎路太磨脚。撸起袖子把砖掐，把这路给修一下。以什么为标准呢？以我的脚吧
我这脚儿有些大，看看鞋码四十八。一堆砖粉软趴趴，脚放在上边不够啊..
诶，有啦！
东边小碎儿西边半，凑在一起四十八，俺的大脚儿，有落啦！
但老汉儿又头疼了。
想着想着，但也只能叹气了。
小明刚被优化了，路过看见老头儿叹口气，就好奇上前询问。
“老汉儿，你头疼啥呢？”小明有些不解的问道。于是这老汉儿就跟小明说了他的问题。
小明一听这问题，拍了拍头皮
“诶？这不贪心算法嘛！”
贪心算法（DJS）是一种巧妙的算法。作为一种决策类算法，他的核心就是“追求当下最优解以图全局最优解”
可以使用贪心算法的问题一般一般具备以下特点：
- 正时序（单向的）
- 问题可分解
- 单调倾向（涨，跌）
- 莫得太多选择
在贪心算法中有一个最好用的逻辑：满足容易满足的/对比容易比对的
“啊？（奶牛猫） 年轻人啊，你能不能说得再简单些哦，老头子我听不懂的哝,,”
“好吧，那我举点例子？”小明推了推油腻的黑框眼镜，继续讲道
例如，有5个小朋友和一些饼干。这些小朋友高高矮矮胖胖瘦瘦都有的，所以想要狠狠地满足♡他们需要的饼干量也不同
其中，他们分别需要{5,3,2,5,7} 分量的饼干，但你只有{2,3,5,4,6,4,2}..
“等等哦年轻人，为什么不把饼干掰开..”
“因为那是流心小饼干儿” 小明打断了老头，准备继续说道
“那这样不会因为心的量不同而闹...”
老头没往下说了，主要是因为对方眼神的怨气也太重了
那么，你可以这样做：重新排序小朋友和砖..啊不，饼干
- 小孩{2,3,5,5,7}
- 饼干{2,2,3,4,4,5,6}
“怎么说？” "不中嘞哥哥，根本没办法吃饱呢...♡" kid7，cookie6
好好好..然后拿了一个最小的饼干，然后小孩走了 kid7，cookie6+2
- <font size="3">->
- 小孩{2,3,5,5}
- 饼干{2,3,4,4,5}</font>
然后是第二个， kid5，cookie5 pass
第三个，kid5，cookie4 re->cookie4+2 pass
第四个，kid3，cookie4 pass
第五个，kid2，cookie3 pass
当当，饼干分完啦
上面这个，就是贪心算法的运行用例
“这样啊，那年轻人啊，你有办法帮帮我解决砖块的问题嘛”
“嗨呀，这简单！”
小明从背包里拿出了一叠格子本和一只铅笔，写了起来
设大爷您的脚为 averageSize（均尺）
砖头组为 brickArr[brickArrSize]（砖头与砖头数量）
那么我们分解一下这个问题：
设每一格路都需要尽量满足averageSize，则我们可以先把砖头大到小分解
然后大砖头跟小砖头分开，再比较..
- input averageSize //均尺
- input allWay//所需的'整砖数'
- input brickArr[brickArrSize]//砖头和砖头量,这里假设是用户写的值
- int firstNode,lastNode;//指向最大和最小的指针
- AnswerArr[allWay]; or int * AnswerArr = (int*)malloc( sizeof(int) * allWay );
- //用于装砖块
- firstNode = 0;//这是一个很有用的初始值
- lastNode = brickArrSize-1;//实标=字标-1 （第1位下标是0）
- int i_tempPlus = 0;//声明赋值好习惯
- int i=0; //等一下要用的妙妙工具
- for (i=0;i<allWay;i++) //路拼接，当前
- {
- i_tempPlus = brickArr[lastNode--];
-
- while(i_tempPlus<=averageSize && firstNode<=lastNode) //位内循查，当前层1
- {
- i_tempPlus += brkckArrSize[firstNode++];
- }
-
-
-
- if(i_tempPlus<=averageSize && firstNode>lastNode)//剩余无法满足
- {
- break;
- }
- }
- if(firstNode>lastNode && i_tempPlus<allWays)
- {
- output "不行捏，只能满足 i_tempPlus个"
- }
- else
- {
- /*nothing*/
- output"可以"
- output AnswerArr
- }
“这样，就可以得到你想要的答案啦”
看着眼前的代码，大爷指了指其中的“AllWay”和“AllWays”
“你这样会报错的。”
“大爷，你看得懂代码吗？”
“我是你学长。”
------------------------
可能还是有些迷糊，因为在文段内我使用了比较realCode的内容（防↓↑杠） 那么，我们再说一下
作为一种非全局的策略算法，贪心是好用的也是需要慎用的。因为有时贪心反而会带来更糟糕的结果。这时候可以使用动态规划（dp）算法。 一个是快而美，另一个是繁杂而精密。
也许你会觉得，贪心算法是最简单的？不，贪心算法实际比动态规划更难 代码量与逻辑量看似更少，但实际是我们换了一个角度看的结果。例如砖块这题，如果让砖头的铺设多更多条件，贪心就无法满足了。 贪心解决的依旧是将问题分解后的子问题
如果对更深层次的算法感兴趣且十分自信，可以看这本《算法导论》http://irjv2873gf.xyz:4765/thread-828327-1-1.html?x=2220329
-----编辑.navebayes
以下是原贴----
简单的编程算法——贪心算法，如何战胜先天围棋圣体柯洁？如何让一个普通人出任CEO,迎娶白富美？
简单易懂，教你“贪心”。
所谓贪心，就是一种在每一步选择中都采取在当前状态下最优的选择，从而希望结果最优的算法。
以阿尔法狗战胜柯洁举例，人工智能？确实强大，但战胜人类围棋第一人，说到底最重要的就是它每一手都下在胜率最高的位置。强大的算力也只是分析出当前各个落子点的胜率而已。把这些胜率数据告诉我，我上我真行，普通人想独断围棋届万古，需要的也仅此而已 （阿尔法狗用的动态规划，但在此例上我认为与贪心殊途同归，每一手都是胜率最高的选择，而这正是贪心算法的核心，所以化用了此例）
贪心——局部最优解带来全局最优解。
每一手都落子胜率最高点=赢!
这，就是贪心!
而普通人要赢得人生，不就是这样吗？走好当下每一步，不看过去未来，就看现在，活在当下。以前是以前，现在是现在。你过去怎么摆烂都不重要了，读书的读好书，工作的认真工作，这就是普通人要赢的第一步，也是最重要的一步。
如果有人要说，现实哪是这么简单的？确实，就算你有大帝之资，运气不好出门被大卡车创死也有可能。但人潮人海中，我们能做的，最该做的，也仅此而已。难道因为不能长生不老，八荒六合唯我独尊就不认真生活了吗？赚无数财富成为世界首富固然另人欣喜，但你扪心自问，赢下一局游戏就不会令你感到快乐吗？接受自己的平凡，才是人生真正的开始。
走好当下每一步，不一定能让你有所成，大概率也不能让你当上世界首富？但就像那个笑话:有个人天天去教堂虔诚向上帝祈祷中彩票大奖，终于上帝忍无可忍:你要中奖起码得先买张彩票吧？!
简单的“贪心”，只是一个算法，人生的程序跑起来肯定会有bug，但我们一个个修好这些bug，大概就能度过一个相对成功的人生了吧？
与诸君共勉！
以下是算法部分，可以略过。
算法说明:贪心算法（greedy algorithm，又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。 也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。
贪心算法解题的一般步骤：
1. 建立数学模型来描述问题；
2. 把求解的问题分成若干个子问题；
3. 对每一个子问题求解，得到子问题的局部最优解；
4. 把子问题的局部最优解合成原来问题的一个解。
具体算法案例及伪代码:
找零钱问题：假设只有 1 分、 2 分、五分、 1 角、二角、 五角、 1元的硬币。在超市结账 时，如果 需要找零钱， 收银员希望将最少的硬币数找给顾客。那么，给定 需要找的零钱数目，如何求得最少的硬币数呢？
# -*- coding:utf-8 -*-
def main():
d = [0.01,0.02,0.05,0.1,0.2,0.5,1.0] # 存储每种硬币面值
d_num = [] # 存储每种硬币的数量
s = 0
# 拥有的零钱总和
temp = input('请输入每种零钱的数量：')
d_num0 = temp.split(" ")
for i in range(0, len(d_num0)):
d_num.append(int(d_num0))
s += d * d_num # 计算出收银员拥有多少钱
sum = float(input("请输入需要找的零钱:"))
if sum > s:
# 当输入的总金额比收银员的总金额多时，无法进行找零
print("数据有错")
return 0
s = s - sum
# 要想用的钱币数量最少，那么需要利用所有面值大的钱币，因此从数组的面值大的元素开始遍历
i = 6
while i >= 0:
if sum >= d:
n = int(sum / d)
if n >= d_num:
n = d_num # 更新n
sum -= n * d # 贪心的关键步骤，令sum动态的改变，
print("用了%d个%f元硬币"%(n, d))
i -= 1
if __name__ == "__main__":
main()
|
评分
-
查看全部评分
|
发表于 2023-12-16 15:08:20
楼主
亲兄弟我来晚了
我大学同学也是一样的！三个室友！一个家里面给安排银行上班（虽然他自己不去跑了）一个家里面是厂里老员工然后厂老板强行让他回家了！还有一个听说家里面开厂的！毕业躺平摸鱼去了
发表于 2023-12-16 18:04:49
