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

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

  •  
  •   guixiexiezou · 111 天前 · 7246 次点击
    这是一个创建于 111 天前的主题,其中的信息可能已经有所发展或是发生改变。

    辞职许久了,思考了很久,觉得自己是不是不太适合当程序员了?最近看算法,刷 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   111 天前   ❤️ 1
    cao
    guixiexiezou
        2
    guixiexiezou   111 天前
    而且代码还是错误的.........哎😔
    v2webdev
        3
    v2webdev   111 天前   ❤️ 1
    矫情的话,去一亩三分地上吧,V 站不适合。
    crclz
        4
    crclz   111 天前   ❤️ 1
    0-1 背包,不要试着去理解它,去感受它。

    多做几个变形题(做不出来看题解也行),自然就理解了。
    darklowly
        5
    darklowly   111 天前   ❤️ 13
    写程序有两大条路

    1 系统类
    2 算法类

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

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

    所以不要灰心。
    BBCCBB
        6
    BBCCBB   111 天前   ❤️ 1
    你要有点基础后就好了, 别气馁.. 刚开始时都是这样, 不停的刷, 总结, 系统的学.

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

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

    背包问题我高中就会解了(自学), 现在还在做运维 , 我是不是比楼主更菜
    wph95
        20
    wph95   111 天前   ❤️ 1
    背包问题一个教程就可以搞定 :)
    https://github.com/tianyicui/pack
    // 背包九讲永远滴神
    gitgabige
        21
    gitgabige   111 天前
    讲道理,我最近也在看(复习)这个。也就看了下简单的 0-1 背包,后面更复杂的就不想看了。我觉得吧,主要是面试公司需要这些,真正工作中用到的凤毛麟角。所谓面试造火箭,工作拧螺丝。
    wph95
        22
    wph95   111 天前
    动归这问题不要慌,这东西是反正常人思路的。不像回溯符合正常人的思维。
    得靠多做题才能逐渐掌握的 (大神除外)
    背包 dp 记忆化搜索 区间 DP 稍微能知道是个啥就足够了
    cccp2020
        23
    cccp2020   111 天前
    动态规划是高阶的算法题了,先学简单的,慢慢再看动态规划,开局就打 boss 绝对是被虐
    gadsavesme
        24
    gadsavesme   111 天前
    不至于啊,不就是多看多练么,我好多题目都是当时花了半天全部参透,写完提交美滋滋,然后过了几个月回来依旧不大记得。但是有的题反复写的多了,基本就忘不掉了。别怀疑自己毕竟都是普通人,那种看过就会,刷一篇就精通的大佬实在是比不来。
    axex
        25
    axex   111 天前
    刷了过几个月忘了
    Gwzlchn
        26
    Gwzlchn   111 天前   ❤️ 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   111 天前
    如果谷歌和栈溢出不能解决问题,那就去 github 里问候作者
    dk7952638
        28
    dk7952638   111 天前   ❤️ 1
    其实绝大多数 IT 从业者从事的并不是软件开发,而是代码焊接工
    QingchuanZhang
        29
    QingchuanZhang   111 天前
    我一开始也不会,别担心,可能只是教程不合适
    westtide
        30
    westtide   111 天前
    可以看 mooc 上的算法课?这些问题在算法课上一般都有讲,还有形式化证明。考研的时候看了北大屈婉玲老师的《算法设计与分析》,讲的很透彻和深刻。
    luckcul
        31
    luckcul   111 天前
    多看 多想 多写
    孰能生巧
    SWALLOWW
        32
    SWALLOWW   111 天前
    我司软件和算法是分开的,各司其职,不难为程序员搞数学
    Martox
        33
    Martox   111 天前
    我都快要忘记我应该刷算法这件事情了
    zzzain46
        34
    zzzain46   110 天前
    哈哈哈当年学 运筹学 的时候也觉得动态规划和背包问题是有点难的,多学几遍就好,先手动模拟原理和方法,再写代码会好很多
    wowodavid
        35
    wowodavid   110 天前
    你要搞明白那些人是“会”了,还是“学会”了,又不是自己想明白的,不就是比你早两天看书看会了吗,有啥好优越的,闻道有先后而已。
    impl
        36
    impl   110 天前 via iPad
    多刷题,不懂的话背下来,找张纸默写几遍,总会有理解的时候
    lithbitren
        37
    lithbitren   110 天前
    动态规划题型太多,背包只是基础,遇到没见过的 DP 题型,除了顶尖大神,剩下基本不可能在面试的时候做出来,所以面试的时候一般就算考动归也是基础动归,多刷刷题就好了
    asanelder
        38
    asanelder   110 天前
    @darklowly #5 前者+1
    raaaaaar
        39
    raaaaaar   110 天前 via Android
    垃圾算法,毁我青春
    RedBeanIce
        40
    RedBeanIce   110 天前   ❤️ 1
    凡尔赛。
    yekern
        42
    yekern   110 天前   ❤️ 1
    刷波数据结构以后在去刷 leetcode
    b00tyhunt3r
        43
    b00tyhunt3r   110 天前
    马一个
    dingyaguang117
        44
    dingyaguang117   110 天前 via iPhone
    题目做多了就有感觉了 和数学一样
    guixiexiezou
        45
    guixiexiezou   110 天前
    认真看了下每个回复,感谢鼓励。昨晚研究了一晚上,终于把基础的 01 背包看懂了,但在二维数组变换成一维数组又看不懂了。关于算法这个,工作中用的概率确实太低太低了(可能和我职业层次位置相对低下有关,之前做游戏服务端,无论是路径计算,技能伤害计算还是常规业务处理,上面的算法我一个都用不到)
    user8341
        46
    user8341   110 天前
    @guixiexiezou 路径计算是不是也要用到算法啊?
    lewis89
        47
    lewis89   110 天前
    @guixiexiezou #45 本来这些算法的意义就不大,至少在 N 很小的时候就没什么卵用,有这个功夫去实现这样花俏的算法,还不如直接全部暴力枚举,你搞一堆剪枝 递推 打表 结果发现 N 很小,维护这个代码的成本远比优化带来的收益高得多,而恰恰大部分场景 N 都很小,所以实际场景 DP 没什么人去用,极少我觉得暴力枚举比 DP 可靠,而且实现容易 测试简单。
    lewis89
        48
    lewis89   110 天前
    @user8341 #46 路径有专门的最短路径算法 还有 R* 这些都是现成的套路算法,只要把游戏里面的地图 弄好成邻接矩阵就行了
    lewis89
        49
    lewis89   110 天前
    @user8341 #46 搞错了应该是 A*算法,最近玩 R 星的游戏太多
    gongshishao126
        50
    gongshishao126   110 天前
    @rodrick 杀人诛心呐~
    lewis89
        51
    lewis89   110 天前
    @Gwzlchn #26 关键是 N 很小的时候,费这么大的劲去搞递推公式的意义真的不大,大部分时候 N 都很小,没必要去实现这样花俏 难以维护的算法,与其这样 为啥不直接暴力枚举?
    no1xsyzy
        52
    no1xsyzy   110 天前
    @darklowly 智商够,但自以为不够的人,是不是无敌了?(
    Chenamy2017
        53
    Chenamy2017   110 天前
    话说作为十年老程序员的我,还没看过 01 背包问题,你钻牛角尖了,程序员有很多方面的,不要揪着算法深入,算法无穷尽,基本的掌握了就可以做业务了。有几个程序员是算法大牛的,市场也不需要那么多的算法大牛。
    justest123
        54
    justest123   110 天前
    是我对凡尔赛的理解有偏差么?为什么这种吐槽+半诉苦的帖子都会有人刷凡尔赛?有病吧

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

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

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

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

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

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

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

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


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


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

    PS:基本的数据结构和算法是需要的。
    gy0624ww
        75
    gy0624ww   107 天前
    特么的,今天我才知道凡尔赛人是啥意思,我以为你们讨论的是一道 leetcode 题目叫凡尔赛人呢
    关于   ·   帮助文档   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2921 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 09:14 · PVG 17:14 · LAX 01:14 · JFK 04:14
    ♥ Do have faith in what you're doing.