【编辑操刀】看不懂你打我，靠贪心算法出任CEO,迎娶白富美

1244220996

& @9 o$ Y& m/ u& h8 _# U4 b8 d今天，小明在街上看见一个在街上叹气的老头儿，老头儿为什么叹气的呢？因为老头儿他今儿有些犟犟的；
地上不是有排砖儿嘛，这路年久失修了砖儿碎得这一块那一块的。老头儿散着步呢，心血来潮想到着
6 h& _8 i, m1 R, @

老汉儿我心情好，看着碎路太磨脚。撸起袖子把砖掐，把这路给修一下。以什么为标准呢？以我的脚吧
4 i$ e2 A( b3 N我这脚儿有些大，看看鞋码四十八。一堆砖粉软趴趴，脚放在上边不够啊..

诶，有啦！

东边小碎儿西边半，凑在一起四十八，俺的大脚儿，有落啦！

; P1 G0 p( C2 y但老汉儿又头疼了。

有点子是有点子，但没办法安排这砖儿啊。

. F1 r! A% @* J
想着想着，但也只能叹气了。

小明刚被优化了，路过看见老头儿叹口气，就好奇上前询问。
“老汉儿，你头疼啥呢？”小明有些不解的问道。于是这老汉儿就跟小明说了他的问题。
' r3 }8 u  \8 N2 R* K小明一听这问题，拍了拍头皮
“诶？这不贪心算法嘛！”
2 `( z9 ]7 V* {& L& S  p

贪心算法（DJS）是一种巧妙的算法。作为一种决策类算法，他的核心就是“追求当下最优解以图全局最优解”
可以使用贪心算法的问题一般一般具备以下特点：
+ _# b8 h, a# {) U7 a6 k7 D1 \/ R$ x

• 正时序（单向的）
• 问题可分解
• 单调倾向（涨，跌）
• 莫得太多选择
  
  5 u/ Q$ |" ?! X* W! Y

8 W3 c7 d: s% r6 m! N在贪心算法中有一个最好用的逻辑：满足容易满足的/对比容易比对的
! @: u2 C0 b, l! N* U  ~8 k( }

4 r2 y. [2 V6 y. ]$ l! L
& e" X$ _( I6 D! B2 ~, E5 ~
“啊？（奶牛猫） 年轻人啊，你能不能说得再简单些哦，老头子我听不懂的哝,,”
, _3 l$ T. c. A
2 p, K/ A" o' F8 h) z( U' r“好吧，那我举点例子？”小明推了推油腻的黑框眼镜，继续讲道

2 O0 l- ?; o* t! k% h例如，有5个小朋友和一些饼干。这些小朋友高高矮矮胖胖瘦瘦都有的，所以想要狠狠地满足♡他们需要的饼干量也不同
% B1 y, ]$ L2 _$ J5 b2 l+ `其中，他们分别需要{5,3,2,5,7} 分量的饼干，但你只有{2,3,5,4,6,4,2}..
: C' ^0 }+ W7 U9 U% v1 q+ k/ W" h

“等等哦年轻人，为什么不把饼干掰开..”
“因为那是流心小饼干儿” 小明打断了老头，准备继续说道
" C' o1 a0 }7 c' c1 V
“那这样不会因为心的量不同而闹...”
% R; u3 X" u) l$ }' I0 k. s老头没往下说了，主要是因为对方眼神的怨气也太重了
9 _3 Q- ^5 s  _/ z
  n: i8 J/ `5 u
那么，你可以这样做：重新排序小朋友和砖..啊不，饼干
6 r) u/ L# X/ v

1. 小孩{2,3,5,5,7}
   
2. 饼干{2,2,3,4,4,5,6}

复制代码

然后一把抓过最大只的小孩和最大的饼干
# O% o1 m5 p$ e; O/ w  }$ v# }“怎么说？” "不中嘞哥哥，根本没办法吃饱呢...♡"  kid7，cookie6

7 W9 [: O( Q' e4 l好好好..然后拿了一个最小的饼干，然后小孩走了 kid7，cookie6+2

1. <font size="3">->
   
2. 小孩{2,3,5,5}
   
3. 饼干{2,3,4,4,5}</font>

复制代码

/ a' s. O3 x: p# _" e+ } 然后是第二个， kid5，cookie5 pass
第三个，kid5，cookie4 re->cookie4+2 pass

; `8 |+ t' Z6 x3 I第四个，kid3，cookie4 pass
第五个，kid2，cookie3 pass

5 \9 @$ y0 O1 x% T& e( J  ]( z( U) O
当当，饼干分完啦
; A/ e, l0 e8 N1 C; ~8 d- o上面这个，就是贪心算法的运行用例
+ d2 z, V3 S0 w8 {
) D5 F9 Q, a* X. Y1 k; r1 A/ a



“这样啊，那年轻人啊，你有办法帮帮我解决砖块的问题嘛”
7 e) [6 K5 r" i) @( A0 G6 s1 L“嗨呀，这简单！”
# b) F+ s0 F7 P& o% v( v小明从背包里拿出了一叠格子本和一只铅笔，写了起来
: |7 c9 \3 d# P9 F" d: p
8 t( U" t" K) Z) O* I设大爷您的脚为 averageSize（均尺）
砖头组为          brickArr[brickArrSize]（砖头与砖头数量）
1 ?" c5 t1 Z/ |* S/ c" n: V+ C, L那么我们分解一下这个问题：
/ @9 f+ }: T# x0 d4 O9 f- D
设每一格路都需要尽量满足averageSize，则我们可以先把砖头大到小分解

1. sort(brickArr)
   

复制代码

然后大砖头跟小砖头分开，再比较..
- l% S4 i3 n1 q8 Y) K

1. input averageSize    //均尺
   $ X/ G6 @# Q+ J2 D
2. input allWay//所需的'整砖数'
   
3. input brickArr[brickArrSize]//砖头和砖头量,这里假设是用户写的值
   $ ~! K, S% M$ W7 s& n  t4 d
4. int firstNode,lastNode;//指向最大和最小的指针
   9 a8 {5 Y( O' U3 Q4 _! O1 @# _
5. 
   ! L# q0 C# ]3 p$ ^
6. AnswerArr[allWay];   or  int * AnswerArr = (int*)malloc( sizeof(int) * allWay );
   
7.     //用于装砖块
   
8. 
   ; Z9 l8 h, }7 h8 v
9. firstNode = 0;//这是一个很有用的初始值
   * K! W/ J; T/ E/ S
10. lastNode = brickArrSize-1;//实标=字标-1 （第1位下标是0）
    
11. 
    
12. int i_tempPlus = 0;//声明赋值好习惯
    
13. 
    
14. int i=0; //等一下要用的妙妙工具
    ; P+ }$ P- e2 t( l
15. 
    
16. for (i=0;i<allWay;i++) //路拼接，当前
    
17. {
    
18.     i_tempPlus = brickArr[lastNode--];
    
19.    
    
20.     while(i_tempPlus<=averageSize && firstNode<=lastNode)  //位内循查，当前层1
    " N3 W. t7 l7 E! A8 W2 [' I
21.     {
    
22.         i_tempPlus += brkckArrSize[firstNode++];
    
23. 
    
24.     }
    
25.    
    
26.    
    4 C( _1 f  f) b3 m. g* u# m
27.   
    4 g9 b5 _% M9 q$ V! Z
28.     if(i_tempPlus<=averageSize && firstNode>lastNode)//剩余无法满足
    
29.     {
    / ]# u* E' |* C% Z
30.         break;
    % C' o0 T2 j4 v- Y' @
31.     }
    & T1 Z# M! d: n2 }
32. }
    7 C# y4 Y8 d7 U. U
33. 
    7 r5 }* y- V5 l, y
34. 
    
35. if(firstNode>lastNode && i_tempPlus<allWays)
    
36. {
    ( G# O" B0 Z: _3 i* V5 T
37.     output "不行捏，只能满足 i_tempPlus个"
    
38. 
    
39. }
    
40. else
    
41. {
    
42.     /*nothing*/
    # X; [4 \  v; H
43.     output"可以"
    7 l  O/ F6 ^$ |/ u# Q: F- b" p: A
44.     output AnswerArr
    5 ]( j3 y) ?, ]
45. 
    
46. }
    

复制代码

: l& g) H7 O. M1 J2 z4 ~7 R( q" W, [
, X0 l) E8 @4 S4 X/ |) H. ]1 R“这样，就可以得到你想要的答案啦”
) A6 X9 U0 f! R: ]' E( I' R
8 D2 P# h) ]. D! G' d
看着眼前的代码，大爷指了指其中的“AllWay”和“AllWays”
“你这样会报错的。”
% z7 W! `+ G% I- {
' G/ \: Z6 N1 K, J2 S$ l$ ?“大爷，你看得懂代码吗？”
“我是你学长。”


3 Q; f# s1 L0 g( z: w/ W" x
: |4 y1 X* M+ N/ [2 G$ Y- R3 X/ _------------------------

. K- B' x0 Q5 ~/ F. `0 U" I1 H4 {可能还是有些迷糊，因为在文段内我使用了比较realCode的内容（防↓↑杠） 那么，我们再说一下


/ ^8 n8 C2 f5 C- b' h& Y作为一种非全局的策略算法，贪心是好用的也是需要慎用的。因为有时贪心反而会带来更糟糕的结果。这时候可以使用动态规划（dp）算法。 一个是快而美，另一个是繁杂而精密。
也许你会觉得，贪心算法是最简单的？不，贪心算法实际比动态规划更难 代码量与逻辑量看似更少，但实际是我们换了一个角度看的结果。例如砖块这题，如果让砖头的铺设多更多条件，贪心就无法满足了。 贪心解决的依旧是将问题分解后的子问题


3 b6 A. i6 \" r2 b
7 W% `( W4 L: |) X8 @7 S, m6 G如果对更深层次的算法感兴趣且十分自信，可以看这本《算法导论》http://irjv2873gf.xyz:4765/thread-828327-1-1.html?x=2220329
0 n: v1 ^6 ^# c1 J0 v* {7 g+ f

! M9 k8 U* T# N0 g
/ n4 `$ H9 m: p( V



; b7 v7 O4 H8 |6 U-----编辑.navebayes
! ~0 @3 ?8 X1 u/ W2 o
0 ?+ d* J) v5 N* E, c! L
+ v9 t+ q  i8 F7 A
2 a, y  E- ?: K4 |0 t
以下是原贴----


$ M6 n" |, L6 r* }

  简单的编程算法——贪心算法，如何战胜先天围棋圣体柯洁？如何让一个普通人出任CEO,迎娶白富美？
   简单易懂，教你“贪心”。
/ O/ ^4 N" k+ Y& d2 n   所谓贪心，就是一种在每一步选择中都采取在当前状态下最优的选择，从而希望结果最优的算法。
   以阿尔法狗战胜柯洁举例，人工智能？确实强大，但战胜人类围棋第一人，说到底最重要的就是它每一手都下在胜率最高的位置。强大的算力也只是分析出当前各个落子点的胜率而已。把这些胜率数据告诉我，我上我真行，普通人想独断围棋届万古，需要的也仅此而已（阿尔法狗用的动态规划，但在此例上我认为与贪心殊途同归，每一手都是胜率最高的选择，而这正是贪心算法的核心，所以化用了此例）
   贪心——局部最优解带来全局最优解。
' Z$ b1 V' i* K   每一手都落子胜率最高点=赢!
5 c' w( P* H; x& Y   这，就是贪心!
   而普通人要赢得人生，不就是这样吗？走好当下每一步，不看过去未来，就看现在，活在当下。以前是以前，现在是现在。你过去怎么摆烂都不重要了，读书的读好书，工作的认真工作，这就是普通人要赢的第一步，也是最重要的一步。
  
   如果有人要说，现实哪是这么简单的？确实，就算你有大帝之资，运气不好出门被大卡车创死也有可能。但人潮人海中，我们能做的，最该做的，也仅此而已。难道因为不能长生不老，八荒六合唯我独尊就不认真生活了吗？赚无数财富成为世界首富固然另人欣喜，但你扪心自问，赢下一局游戏就不会令你感到快乐吗？接受自己的平凡，才是人生真正的开始。
- f+ b4 p1 b8 ~   走好当下每一步，不一定能让你有所成，大概率也不能让你当上世界首富？但就像那个笑话:有个人天天去教堂虔诚向上帝祈祷中彩票大奖，终于上帝忍无可忍:你要中奖起码得先买张彩票吧？!  
   简单的“贪心”，只是一个算法，人生的程序跑起来肯定会有bug，但我们一个个修好这些bug，大概就能度过一个相对成功的人生了吧？
$ c1 c9 C: ]. Y8 l$ w% V6 k7 m; m) a( B   与诸君共勉！

; V- y4 v7 \. S; d# v% A* n以下是算法部分，可以略过。
3 N/ c# z/ q/ e8 ~7 O: |2 D  x算法说明:贪心算法（greedy algorithm，又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。 也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。

贪心算法解题的一般步骤：
1. 建立数学模型来描述问题；
2. 把求解的问题分成若干个子问题；
3. 对每一个子问题求解，得到子问题的局部最优解；
4 [/ W( f: c$ w4 N1 `3 R4. 把子问题的局部最优解合成原来问题的一个解。
" m1 ?1 t% v5 B$ }1 W- Z" S具体算法案例及伪代码:
- [7 o% a; T4 R& I* I7 X* K4 p找零钱问题：假设只有 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 = [] # 存储每种硬币的数量
/ d. E$ z$ c( }) {    s = 0
' m" }# b2 k. L" \    # 拥有的零钱总和
. ^+ }0 K3 n6 C: S1 @8 `* f; S    temp = input('请输入每种零钱的数量：')
    d_num0 = temp.split(" ")
* p7 R) m9 U; s1 H5 ?- s; [
    for i in range(0, len(d_num0)):
        d_num.append(int(d_num0))
        s += d * d_num # 计算出收银员拥有多少钱

/ s: D- \/ `' }; r! g    sum = float(input("请输入需要找的零钱:"))

5 m5 t, S: Q7 `7 w    if sum > s:
        # 当输入的总金额比收银员的总金额多时，无法进行找零
/ X* H1 u* e2 O$ E: J        print("数据有错")
        return 0

    s = s - sum
    # 要想用的钱币数量最少，那么需要利用所有面值大的钱币，因此从数组的面值大的元素开始遍历
0 m5 E% F3 ?- l/ @8 [5 ~) J    i = 6
; n9 t& ?2 {* m- q+ G9 q  u6 H    while i >= 0:
        if sum >= d:
            n = int(sum / d)
! q9 A8 z& J& D' v3 k; Y% e/ r            if n >= d_num:
# U, r) D8 j+ W+ i/ Y$ o                n = d_num  # 更新n
$ u0 N' B7 a5 \. m            sum -= n * d # 贪心的关键步骤，令sum动态的改变，
            print("用了%d个%f元硬币"%(n, d))
        i -= 1

if __name__ == "__main__":
main()
+ g% T( I% [& u

a153588701

好好好，都能看懂是吧，感情老王就我一个铁废物，想起大学三个舍友，毕业一个马上就考上了公务员，两个家里直接给找好了工作，就我一个人傻逼呵呵的跟他们玩好几年，一毕业发现就我一个真废物

白驫

狐狸说葡萄，你看懂了没?
: }0 M, i+ [8 k3 R* o
S（n）是一个集合，集合里有六个元素，
0 \3 {$ b/ c6 C5 S第一个元素S（1）他的值是0.01
. ~, S9 n1 u( q( ES（1）他的值是0.02
...
- n) C( s# L/ f7 d7 T) ]S（6）值为1
6 D1 [* ]/ L' c* f7 b" Y; \# O. t* c
  L6 _/ R. i: z: f" o2 y6 dSu（n）一个集合，同样六个元素
( B% m/ u/ l$ k+ s  m1 B这个集合多少个个元素由玩家输入这里输入的就是收银员的币存。
8 h# T; a3 ]+ X6 N/ G/ [
有了S（n）和Su（n）就算下总，这个总我们用d表示。这个总就是收银员现有的总钱

, [# j& g: R! v4 O1 I. k; G然后又要你输入一个该扣除的钱数f

因为要尽量可能给出大面值硬币所以遍历从6开始递减是S（6）S（5）如此下去到S（1）
$ k9 J7 n( c+ [6 H- ?3 U, y, `8 ?& ^& e该扣除钱数f－（当前币值S（n）×当前币存的尽可能最大数）且f≠负数
每次钱扣除当前币值后余数去下一个币值再去减。
最后就是这样的，最后一堆找零。我有点忘了开头引用的是什么库。狐狸说葡萄，集合应该不是大学矩阵群环，应该不会也读不懂吧。当然其实还可以行列式一句搞定。

postqt

a153588701 发表于 2023-12-16 20:04
1 x& r3 U: r/ r+ l' F$ @3 p0 @好好好，都能看懂是吧，感情老王就我一个铁废物，想起大学三个舍友，毕业一个马上就考上了公务员，两个家里 ...

( ~  z/ v2 q" ]9 ^亲兄弟我来晚了我大学同学也是一样的！三个室友！一个家里面给安排银行上班（虽然他自己不去跑了）一个家里面是厂里老员工然后厂老板强行让他回家了！还有一个听说家里面开厂的！毕业躺平摸鱼去了

Applcu

navebayes 发表于 2023-12-17 11:47
@Applcu 可以看一下操刀后，这是我期望的水准来着。。

7 Q* m& ^* b+ z, `) t实话讲，第20到24行，有一些问题，部分特例是不太满足的，这个代码应对大多数这种拼砖问题都是可行的，但问题在于如果lastNode及前面lastNode-n个是一个接近于averageSize的值，同时其他值是趋近于二分之一averageSize的时候，并且需要的砖数小于n，这看起来就没这么合理了。理论上要找到这样的最优解，只能强行穷举所有可能，然后对比他们的距离（平方即可）再进行排列，取出前面误差最小的几个值组成数列，如果要求严格大于或小于averageSize，那么也可用一个if判断。当然计算量确实可怕。
3 O* t0 m* Z: K

白驫

看到了，数组会用为什么多维数组的矩阵运算就不会呢？你是计算机的吗？数学模型很多需要计算机辅助的。

navebayes

这编辑器又发颠了？？

navebayes

白驫 发表于 2023-12-16 18:03
8 X% H5 J& {/ ~; b) [  u7 m6 V; K看到了，数组会用为什么多维数组的矩阵运算就不会呢？你是计算机的吗？数学模型很多需要计算机辅助的。 ...

( y( T# L$ A8 W# Q- a因为这里在讲贪心算法

navebayes

a153588701 发表于 2023-12-16 20:04
好好好，都能看懂是吧，感情老王就我一个铁废物，想起大学三个舍友，毕业一个马上就考上了公务员，两个家里 ...

原来的评论有很多不懂的，但评论不知道为什么不见了。术业有专攻很正常

昔有佳人公孙氏

贪心算法很强大。很多计算机相关算法都有他的影子。无论是银行家算法还是哲学家吃饭
唉 算了 我还是复习去吧 越说心里越没底 还好这破玩意初试不考

navebayes

昔有佳人公孙氏 发表于 2023-12-16 22:32
贪心算法很强大。很多计算机相关算法都有他的影子。无论是银行家算法还是哲学家吃饭
唉 算了 我还是复习去 ...

! q! G# U0 b$ h确实，虽然写着挺简单但实际比动态规划更难，主要是靠拆分问题的能力

navebayes

@Applcu 可以看一下操刀后，这是我期望的水准来着。。

Applcu

navebayes 发表于 2023-12-17 11:47
@Applcu 可以看一下操刀后，这是我期望的水准来着。。

3 T$ D. b' G9 W! j. V0 m你们再这么搞，过两天这论坛成了计算机学生的耶路撒冷...黄网界的力扣
: G  _( W# @: u4 d3 T7 T1 P2 E

Applcu

navebayes 发表于 2023-12-17 11:47
* E# }! O, Z1 k! E$ W4 z@Applcu 可以看一下操刀后，这是我期望的水准来着。。

$ F6 G. v8 r0 D3 m6 ?' q我想到了之前大一做的一个题，算很经典的题目，就是小青蛙跳台阶，如果这个小青蛙一次只能跳1或3个台阶，请列举小青蛙跳n个台阶的跳法种数，异曲同工之处，当然也有一些不同点
4 F& ]1 I/ t8 C7 N# U" X

navebayes

5 f* }3 N( r, O8 Q4 h' ]

Applcu 发表于 2023-12-17 13:25
4 Y" X; F6 U# m/ z& m" w. }实话讲，第20到24行，有一些问题，部分特例是不太满足的，这个代码应对大多数这种拼砖问题都是可行的，但 ...

  ^$ w. q3 |! D是的，这代码如果遇到案例值相差极大时难以满足，如果要解决的话需要改一下标记结构，摸了 用这个编辑器写代码太折磨了。。
虽然在实际运行环境会使用低精度离散哨兵（lowDispFlag）作为辅助维护器
大致可以理解为把尺寸分割为不同阶然后用安插哨兵子并且用散列储存，这样做可以保持在nlog+C

navebayes

Applcu 发表于 2023-12-17 13:25
实话讲，第20到24行，有一些问题，部分特例是不太满足的，这个代码应对大多数这种拼砖问题都是可行的，但 ...

  G* u& a1 Q8 ^哦不是二巡，是需要改变标记结构

navebayes

Applcu 发表于 2023-12-17 13:32
, Z; j4 c3 ]/ V9 s3 D我想到了之前大一做的一个题，算很经典的题目，就是小青蛙跳台阶，如果这个小青蛙一次只能跳1或3个台阶， ...

那个是dp题

Applcu

navebayes 发表于 2023-12-17 13:39
# ^, H! X! J* X6 w+ d  ]) L是的，这代码如果遇到案例值相差极大时难以满足，如果要解决的话可以进行低位二巡；不过还要多写一个循环 ...

/ F" V1 t+ t! v9 f* X6 G2 A太顶了你是真正的大佬
% {5 V2 M5 _; [/ R, i

navebayes

Applcu 发表于 2023-12-17 13:50
太顶了你是真正的大佬

不至于不至于不至于(=ﾟДﾟ=)   只是去年的时候玩过一些算法 所以用自己知道的说出这些而已...  其实算法思路都差不多的，理解为数学题那样的形式，然后用函数解题就行了

navebayes

Applcu 发表于 2023-12-17 13:50
太顶了你是真正的大佬

& k# d6 s% k. Y# ~/ C/ c0 ^
. l& S& d1 @: n, v: n9 i6 [而且你也很不错啊，第一眼就看出问题在哪里了。如果你感兴趣的话，也可以写一些帖子，这样就有理由给你打赏了(´,,•ω•,,｀)
* a5 P. @* g# \) ~. |% g这里终究是论坛，不是我的博客，内容都是得靠大家的..

Applcu

navebayes 发表于 2023-12-17 14:04
) A# U; D% `- @9 w7 v而且你也很不错啊，第一眼就看出问题在哪里了。如果你感兴趣的话，也可以写一些帖子，这样就有理由给你打 ...

6 l' h$ p- c7 N/ ^  p: d好的好的，我尽量写帖子哦
! G6 r2 n% s: c2 J