V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
guixiexiezou
V2EX  ›  程序员

连 01 背包都看不懂, 零钱兑换都不会,还能继续走 Coding 这条路吗

  •  
  •   guixiexiezou · 2020-11-16 12:10:29 +08:00 · 8825 次点击
    这是一个创建于 1452 天前的主题,其中的信息可能已经有所发展或是发生改变。

    辞职许久了,思考了很久,觉得自己是不是不太适合当程序员了?最近看算法,刷 leetcode,简单的基本都会(相信在做的各位也没几个不会的),遇到最优解的,动态规划的,基本一个都不会了(哭。。。)

    然后昨天今天特意看了下 01 背包问题,我发现我居然看不懂了。。。

    今天看到一个简单的零钱兑换问题。只会用回溯法。。。我是不是没救了。。。

    附代码

    private int change0(int[] arr, int target) {
            Arrays.sort(arr);
            ArrayDeque<Integer> stack = new ArrayDeque<>();
            int index = arr.length-1;
            while (!stack.isEmpty() || index >= 0) {
                if (index < 0) {
                    if (stack.isEmpty()) return -1; //找不到
                    int last = stack.pop();
                    target += arr[last];
                    index = last-1;
                    continue;
                }
                if (arr[index] == target) {
                    return stack.size()+1;
                } else if (arr[index] > target) {
                    index--;
                } else {
                    target -= arr[index];
                    stack.push(index);
                }
            }
            return -1;
    }
    
    75 条回复    2020-11-20 14:26:28 +08:00
    hubahuba
        1
    hubahuba  
       2020-11-16 12:17:02 +08:00   ❤️ 1
    cao
    guixiexiezou
        2
    guixiexiezou  
    OP
       2020-11-16 12:25:42 +08:00
    而且代码还是错误的.........哎😔
    v2webdev
        3
    v2webdev  
       2020-11-16 12:26:48 +08:00   ❤️ 1
    矫情的话,去一亩三分地上吧,V 站不适合。
    crclz
        4
    crclz  
       2020-11-16 12:29:14 +08:00   ❤️ 1
    0-1 背包,不要试着去理解它,去感受它。

    多做几个变形题(做不出来看题解也行),自然就理解了。
    darklowly
        5
    darklowly  
       2020-11-16 12:30:46 +08:00   ❤️ 13
    写程序有两大条路

    1 系统类
    2 算法类

    系统类,不需要那么多的算法,简单的数据,链表,树,hash 就够了。其他的就是计算机系统方面的知识。例如,组成原理,操作系统,设计模式,架构模式。这条路适合智力正常范围的人,因为智力正常的人,更容易感受到困难,就更容易设计简单的系统,反而对设计有好处。

    算法类,侧重点就是数学,适合智力好一点的人,反而这类人不容易感受到困难,设计的系统会违反常人的直觉,反而是不好的设计。当然也有很多智商不够,自以为很够的人,既设计不好算法,又搞的很复杂。

    所以不要灰心。
    BBCCBB
        6
    BBCCBB  
       2020-11-16 12:35:07 +08:00   ❤️ 1
    你要有点基础后就好了, 别气馁.. 刚开始时都是这样, 不停的刷, 总结, 系统的学.

    0-1 背包可以看看这个 https://www.cnblogs.com/labuladong/p/12455089.html
    guixiexiezou
        7
    guixiexiezou  
    OP
       2020-11-16 12:53:42 +08:00
    @v2webdev 可能是太久没工作了吧,心又静不下来。多谢指点
    guixiexiezou
        8
    guixiexiezou  
    OP
       2020-11-16 12:55:30 +08:00
    @darklowly 嗯嗯,多谢指点。我也觉得我如果继续 coding 下去,最多最多还是只能走工程这条路,也就是所谓的用别别人的轮子
    guixiexiezou
        9
    guixiexiezou  
    OP
       2020-11-16 12:55:54 +08:00
    @BBCCBB 多谢,我去看看
    guixiexiezou
        10
    guixiexiezou  
    OP
       2020-11-16 12:56:37 +08:00
    @crclz 我再感受 2 天吧,说不定真就领悟了
    rodrick
        11
    rodrick  
       2020-11-16 12:59:14 +08:00
    不要灰心,换个角度想想,你如果转行了又怎么知道自己更适合另外一行呢
    deepall
        12
    deepall  
       2020-11-16 13:19:40 +08:00   ❤️ 7
    这不是凡尔赛人?
    tgich
        13
    tgich  
       2020-11-16 13:26:23 +08:00
    @deepall 这不就是凡尔赛人
    a62527776a
        14
    a62527776a  
       2020-11-16 13:30:04 +08:00
    太牛了(吹捧一波
    keymao
        15
    keymao  
       2020-11-16 13:32:38 +08:00
    这不就是凡尔赛人
    guchengyehai1
        16
    guchengyehai1  
       2020-11-16 13:38:02 +08:00 via Android
    回溯再加个记忆就和 dp 差不多了
    Mac
        17
    Mac  
       2020-11-16 13:38:45 +08:00 via Android   ❤️ 1
    我只会百度谷歌,其它的一概不会
    shubo83
        18
    shubo83  
       2020-11-16 13:42:45 +08:00
    可以先当不会算法的野生程序员,比如我
    leido
        19
    leido  
       2020-11-16 13:45:33 +08:00
    楼主, 背包九讲看了吗?

    DP 根本算不上什么高级算法, 扯不到什么系统和算法上去 @darklowly

    背包问题我高中就会解了(自学), 现在还在做运维 , 我是不是比楼主更菜
    wph95
        20
    wph95  
       2020-11-16 13:47:40 +08:00   ❤️ 1
    背包问题一个教程就可以搞定 :)
    https://github.com/tianyicui/pack
    // 背包九讲永远滴神
    gitgabige
        21
    gitgabige  
       2020-11-16 13:48:22 +08:00
    讲道理,我最近也在看(复习)这个。也就看了下简单的 0-1 背包,后面更复杂的就不想看了。我觉得吧,主要是面试公司需要这些,真正工作中用到的凤毛麟角。所谓面试造火箭,工作拧螺丝。
    wph95
        22
    wph95  
       2020-11-16 13:51:08 +08:00
    动归这问题不要慌,这东西是反正常人思路的。不像回溯符合正常人的思维。
    得靠多做题才能逐渐掌握的 (大神除外)
    背包 dp 记忆化搜索 区间 DP 稍微能知道是个啥就足够了
    cccp2020
        23
    cccp2020  
       2020-11-16 13:54:11 +08:00
    动态规划是高阶的算法题了,先学简单的,慢慢再看动态规划,开局就打 boss 绝对是被虐
    gadsavesme
        24
    gadsavesme  
       2020-11-16 14:01:30 +08:00
    不至于啊,不就是多看多练么,我好多题目都是当时花了半天全部参透,写完提交美滋滋,然后过了几个月回来依旧不大记得。但是有的题反复写的多了,基本就忘不掉了。别怀疑自己毕竟都是普通人,那种看过就会,刷一篇就精通的大佬实在是比不来。
    axex
        25
    axex  
       2020-11-16 14:09:40 +08:00
    刷了过几个月忘了
    Gwzlchn
        26
    Gwzlchn  
       2020-11-16 14:11:41 +08:00   ❤️ 4
    楼主您好~我是来鼓励你的 hhh

    我这学期刚选了我们学校的算法课(卜东波教授),实际上,老师上课也会说,DP 、贪心算法的每个细微的策略并不是那么显然的,我们不可能对每道题都背诵算法的策略,重要的是我们应该如何从问题的特点构造出来一种合适的策略。

    举个例子,我看楼上有说“九讲背包”这个文档不错,那么我对下面这句话问几个问题希望楼主思考一下:为什么我们要在状态方程中使用“前 i 个物品”这种定义状态转移的策略?如果用“前 i 个”这种表述,那么我们对物品集合进行排序了吗(注意,集合是无序的,所以你不能对一个集合说“前 i 个”)?如果是排序的,那么我们应该用什么样的定序方法?

    或者考虑这种更新子问题的策略:我们每步都考虑物品集合中的每个物品是否能放入背包中,然后下一步进行同样的策略呢?这种方法可不可行呢?

    “用子问题定义状态:即 F[i, v] 表示前 i 件物品恰放入一个容量为 v 的背包可以获得的最大价值。则其状态转移方程便是:F[i, v] = max{F[i − 1, v], F[i − 1, v − Ci] + Wi}


    你看,这个 01 背包物品问题真的每步都不是那么显然成立的,所以觉得难是正常的。如果你觉得简单,而并没有仔细思考这些问题只能说明你是背会的答案,而不是理解会的,那又有什么意义呢?

    总而言之:觉得难是好事,这会促进我们思考算法中每个不那么显然的地方。
    dk7952638
        27
    dk7952638  
       2020-11-16 14:46:31 +08:00
    如果谷歌和栈溢出不能解决问题,那就去 github 里问候作者
    dk7952638
        28
    dk7952638  
       2020-11-16 14:47:38 +08:00   ❤️ 1
    其实绝大多数 IT 从业者从事的并不是软件开发,而是代码焊接工
    QingchuanZhang
        29
    QingchuanZhang  
       2020-11-16 15:08:47 +08:00
    我一开始也不会,别担心,可能只是教程不合适
    westtide
        30
    westtide  
       2020-11-16 15:16:09 +08:00
    可以看 mooc 上的算法课?这些问题在算法课上一般都有讲,还有形式化证明。考研的时候看了北大屈婉玲老师的《算法设计与分析》,讲的很透彻和深刻。
    luckcul
        31
    luckcul  
       2020-11-16 15:27:03 +08:00
    多看 多想 多写
    孰能生巧
    SWALLOWW
        32
    SWALLOWW  
       2020-11-16 16:49:19 +08:00
    我司软件和算法是分开的,各司其职,不难为程序员搞数学
    Martox
        33
    Martox  
       2020-11-16 16:54:51 +08:00
    我都快要忘记我应该刷算法这件事情了
    zzzain46
        34
    zzzain46  
       2020-11-16 19:06:49 +08:00
    哈哈哈当年学 运筹学 的时候也觉得动态规划和背包问题是有点难的,多学几遍就好,先手动模拟原理和方法,再写代码会好很多
    wowodavid
        35
    wowodavid  
       2020-11-16 20:04:03 +08:00
    你要搞明白那些人是“会”了,还是“学会”了,又不是自己想明白的,不就是比你早两天看书看会了吗,有啥好优越的,闻道有先后而已。
    impl
        36
    impl  
       2020-11-16 21:50:56 +08:00 via iPad
    多刷题,不懂的话背下来,找张纸默写几遍,总会有理解的时候
    lithbitren
        37
    lithbitren  
       2020-11-16 22:08:53 +08:00
    动态规划题型太多,背包只是基础,遇到没见过的 DP 题型,除了顶尖大神,剩下基本不可能在面试的时候做出来,所以面试的时候一般就算考动归也是基础动归,多刷刷题就好了
    asanelder
        38
    asanelder  
       2020-11-16 22:32:20 +08:00
    @darklowly #5 前者+1
    raaaaaar
        39
    raaaaaar  
       2020-11-16 22:37:19 +08:00 via Android
    垃圾算法,毁我青春
    RedBeanIce
        40
    RedBeanIce  
       2020-11-16 22:40:52 +08:00   ❤️ 1
    凡尔赛。
    yekern
        42
    yekern  
       2020-11-17 07:31:49 +08:00   ❤️ 1
    刷波数据结构以后在去刷 leetcode
    b00tyhunt3r
        43
    b00tyhunt3r  
       2020-11-17 08:47:11 +08:00
    马一个
    dingyaguang117
        44
    dingyaguang117  
       2020-11-17 09:20:58 +08:00 via iPhone
    题目做多了就有感觉了 和数学一样
    guixiexiezou
        45
    guixiexiezou  
    OP
       2020-11-17 09:53:24 +08:00
    认真看了下每个回复,感谢鼓励。昨晚研究了一晚上,终于把基础的 01 背包看懂了,但在二维数组变换成一维数组又看不懂了。关于算法这个,工作中用的概率确实太低太低了(可能和我职业层次位置相对低下有关,之前做游戏服务端,无论是路径计算,技能伤害计算还是常规业务处理,上面的算法我一个都用不到)
    user8341
        46
    user8341  
       2020-11-17 10:06:58 +08:00
    @guixiexiezou 路径计算是不是也要用到算法啊?
    lewis89
        47
    lewis89  
       2020-11-17 10:45:37 +08:00
    @guixiexiezou #45 本来这些算法的意义就不大,至少在 N 很小的时候就没什么卵用,有这个功夫去实现这样花俏的算法,还不如直接全部暴力枚举,你搞一堆剪枝 递推 打表 结果发现 N 很小,维护这个代码的成本远比优化带来的收益高得多,而恰恰大部分场景 N 都很小,所以实际场景 DP 没什么人去用,极少我觉得暴力枚举比 DP 可靠,而且实现容易 测试简单。
    lewis89
        48
    lewis89  
       2020-11-17 10:46:50 +08:00
    @user8341 #46 路径有专门的最短路径算法 还有 R* 这些都是现成的套路算法,只要把游戏里面的地图 弄好成邻接矩阵就行了
    lewis89
        49
    lewis89  
       2020-11-17 10:47:22 +08:00
    @user8341 #46 搞错了应该是 A*算法,最近玩 R 星的游戏太多
    gongshishao126
        50
    gongshishao126  
       2020-11-17 10:48:52 +08:00
    @rodrick 杀人诛心呐~
    lewis89
        51
    lewis89  
       2020-11-17 10:55:52 +08:00
    @Gwzlchn #26 关键是 N 很小的时候,费这么大的劲去搞递推公式的意义真的不大,大部分时候 N 都很小,没必要去实现这样花俏 难以维护的算法,与其这样 为啥不直接暴力枚举?
    no1xsyzy
        52
    no1xsyzy  
       2020-11-17 10:59:03 +08:00
    @darklowly 智商够,但自以为不够的人,是不是无敌了?(
    Chenamy2017
        53
    Chenamy2017  
       2020-11-17 11:01:28 +08:00
    话说作为十年老程序员的我,还没看过 01 背包问题,你钻牛角尖了,程序员有很多方面的,不要揪着算法深入,算法无穷尽,基本的掌握了就可以做业务了。有几个程序员是算法大牛的,市场也不需要那么多的算法大牛。
    justest123
        54
    justest123  
       2020-11-17 11:01:55 +08:00
    是我对凡尔赛的理解有偏差么?为什么这种吐槽+半诉苦的帖子都会有人刷凡尔赛?有病吧

    数学思维或者说逻辑思维不是非常好,这类算法题一样也是感觉头大,倒是没怀疑自己没救了,大概还是看开点,什么能力做什么事,难为自己干嘛呢
    Phariel
        55
    Phariel  
       2020-11-17 11:05:58 +08:00 via iPhone
    自信点 我有些 easy 也做不到最优解 你太魔怔了🐶
    Felldeadbird
        56
    Felldeadbird  
       2020-11-17 11:14:12 +08:00
    CURD 也是一件快活牛逼的事情。写软件又不是时刻用到算法。
    vevlins
        57
    vevlins  
       2020-11-17 11:24:55 +08:00   ❤️ 1
    不会算法的程序员多的是。

    程序员的三个方向:性能的极致优化、业务的极致理解、系统的极致设计。做到一个就可以了。
    coderunI
        58
    coderunI  
       2020-11-17 11:31:22 +08:00
    看不起,代码焊接工吗?
    learningman
        59
    learningman  
       2020-11-17 11:33:05 +08:00
    看不起,手上没几块 ICPC World Final Gold 配写代码? NOI 国集估计也就勉强写写 CURD 吧
    cumshot
        60
    cumshot  
       2020-11-17 11:42:53 +08:00
    不能
    tianhualefei
        61
    tianhualefei  
       2020-11-17 13:49:40 +08:00 via Android
    背包问题在力扣( leetcode )属于中等难度。你这既没有正确认识问题的难度,也没正确认识自己的水平。
    totoro52
        62
    totoro52  
       2020-11-17 13:54:48 +08:00
    这里也有凡尔赛人?
    guixiexiezou
        63
    guixiexiezou  
    OP
       2020-11-17 14:05:58 +08:00
    @tianhualefei 我看了下,确实是属于中等难度。也就是说这就是我思维的极限了。
    ochatokori
        64
    ochatokori  
       2020-11-17 14:07:37 +08:00 via Android
    我只会快排,我应该转行吗
    guixiexiezou
        65
    guixiexiezou  
    OP
       2020-11-17 14:08:34 +08:00
    @totoro52 当你所有视频面(中大厂级别)都挂了的时候,也许你就不会这么认为了,反而会从另外一个角度思考问题,无论是牛角尖也好,还是感悟人生也好
    guixiexiezou
        66
    guixiexiezou  
    OP
       2020-11-17 14:11:12 +08:00
    @user8341 寻路一般都用改进版 A 星算法,一般都用现成的库例如 LIBGDX 等,也会用上一代人遗留的代码,直接调用接口。需要自己完整实现的场景不多
    jay4497
        67
    jay4497  
       2020-11-17 14:52:25 +08:00
    哪条路上都有各种级别的人,大神都那么多了,咱就不去凑那个热闹了,安心做个菜鸡。。。

    说不适合这条路那不至于不至于。。。
    billma
        68
    billma  
       2020-11-17 16:45:17 +08:00
    你这让只会 vb 的我情何以堪...
    calabash519
        69
    calabash519  
       2020-11-17 16:53:17 +08:00
    建议转行
    weidaizi
        70
    weidaizi  
       2020-11-17 17:15:28 +08:00
    @darklowly 十分认同
    1039460820
        71
    1039460820  
       2020-11-17 18:14:12 +08:00
    小白前来为楼主加油,随便看看大佬们的推荐,V2ex 万岁!
    CoderGeek
        72
    CoderGeek  
       2020-11-17 18:21:40 +08:00
    用过就忘 老被说 公司里经常被人怼 不是会个啥算法就怎么样,然后离职换下家又得温习一遍 哈哈哈
    hejw19970413
        73
    hejw19970413  
       2020-11-17 18:28:18 +08:00
    先会学会抄,后会学,然后是理解,这是一个痛苦的过程
    darklowly
        74
    darklowly  
       2020-11-17 22:00:58 +08:00
    @leido 和算法高不高级么关系的,重要是两条不同的方向。不信的话,你可以调研一下绝大部分工程师,工作中用过动态规划吗?

    绝大部份工程师职业瓶颈根本就不在算法上面,是在设计上面,能够用简单优美的方法解决问题,比算法更重要。

    我观察过很多工程师,智力正常,投资很多时间去搞算法,结果是,算法也搞不好,代码也写不好,这种情况在国内非常普遍。甚至很多工程师工作 10 年以上,分解一个函数都分解不好。

    go 语言有一个开源的 web 框架:beego,在国内受到了大量的追捧,里面的代码写得非常差,设计也非常潦草。如果你仔细去思考这个问题,会非常有意思:

    1 为什么一个喜欢技术的程序员写出了非常差的代码,还好意思公开发表?并且还出书教人?

    2 为什么大量的用户会去追捧这样一个很差的框架?这些用户里面大量是小白,没有鉴别能力,可以理解,为什么很多很有经验的工程师也没有鉴别能力?如果连基本的鉴别能力都不具备,设计能力就更不具备了。


    他们缺乏的是算法能力吗?还是基本的设计能力和鉴别能力?


    这些设计和鉴别能力,应该怎么才能学到呢?无非就是去多学习经典的设计方法。而这些设计方法大多在第一条路上面学习。

    PS:基本的数据结构和算法是需要的。
    gy0624ww
        75
    gy0624ww  
       2020-11-20 14:26:28 +08:00
    特么的,今天我才知道凡尔赛人是啥意思,我以为你们讨论的是一道 leetcode 题目叫凡尔赛人呢
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3850 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 39ms · UTC 10:20 · PVG 18:20 · LAX 02:20 · JFK 05:20
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.