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

阿里面试命中率最高的基础考题,你真的掌握了吗?

  •  
  •   hakunamatata11 · 2020-02-17 16:18:31 +08:00 · 1378 次点击
    这是一个创建于 1744 天前的主题,其中的信息可能已经有所发展或是发生改变。

    背包问题 (Knapsack problem) 是一种组合优化的 NP 完全问题。

    一般来说,就是给定一组有固定价值和固定重量的物品,以及一个已知最大承重量的背包,求在不超过背包最大承重量的前提下,能放进背包里面的物品的最大总价值。

    image

    如果用一句话形象地描述,大概就是:有个小偷半夜闯入豪宅,可以偷的东西非常多,但是负重能力有限,偷哪些东西才更加不枉此行?

    这一类问题是典型的使用动态规划解决的问题,我们可以把背包问题分成 3 种不同的子问题:0-1 背包问题、完全背包和多重背包问题,剩下一些都是这 3 种的变形以及组合。

    • 01 背包

    有 N 件物品和一个容量为 V 的背包,第 i 件物品消耗的容量为 Ci,价值为 Wi,求解放入哪些物品可以使得背包中总价值最大。

    • 完全背包

    有 N 种物品和一个容量为 V 的背包,每种物品都有无限件可用,第 i 件物品消耗的容量为 Ci,价值为 Wi,求解放入哪些物品可以使得背包中总价值最大。

    • 多重背包

    有 N 种物品和一个容量为 V 的背包,第 i 种物品最多有 Mi 件可用,每件物品消耗的容量为 Ci,价值为 Wi,求解放入哪些物品可以使得背包中总价值最大。

    2.背包问题的难点在哪里?

    三种背包问题都有一个共同的限制,那就是背包容量,背包的容量是有限的,这便限制了物品的选择,而三种背包问题的共同目的,便是让背包中的物品价值最大。

    不同的地方在于物品数量的限制,不过虽然三种背包问题对于物品数量的限制不一样,但都可以转化为 01 背包问题来进行思考。 所以说,01 背包问题是所有背包问题的基础,弄懂了 01 背包问题后,完全背包和多重背包就没有什么困难的地方了

    image

    但真正在面试中,你可能会遇到很多背包问题的变形。如果你没有一双火眼金睛,一眼看出题目的本质其实是个背包问题,你可能会走很多弯路。 如:

    • Target sum 问题( LintCode 链接:Target sum
    • Airbnb 的 menu order 问题(点菜,菜的价格为 double, 问如何正好花完手中的钱)

    本质上都是背包问题,很多同学没有看透问题的真面目,会觉得每道题都是独立的,很难做到举一反三,于是就深陷其中不得章法,如果把背包问题的几种类型都弄懂,类似的很多题其实都能迎刃而解了。

    如果你不会辨别背包问题,去听《背包四讲》吧,里面讲了很多 Facebook,Google,BAT 等大厂的面试高频题(领取方式见文末)。

    3.01 背包问题及其题解

    背包问题都有哪些经典例题呢?

    01 背包

    在 N 个物品中挑选若干物品装入背包,最多能装多满? 假设背包的大小为 V,第 i 个物品的大小为 C[i] 注意:你不可以将物品进行切割。

    有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的费用是 Ci,得到的价值是 Wi。求解将哪些物品装入背包可使价值总和最大?

    如果你想把这个知识点学得更透彻,可以听一听《背包四讲基础知识和刷题都覆盖到了

    这门原价$199 的课程,现在$1 秒杀!

    参与方式:

    戳我免费试听后,添加九章 Sunny 微信 jiuzhang15,回复 [ V2EX 背包] + 试听报名截图即可一美元购买本课程

    2 条回复    2020-02-18 15:36:43 +08:00
    richard1122
        1
    richard1122  
       2020-02-18 11:28:24 +08:00
    为啥不学免费的背包 “九” 讲,要学付费的 “四” 讲?。。

    https://raw.githubusercontent.com/tianyicui/pack/master/V2.pdf
    hakunamatata11
        2
    hakunamatata11  
    OP
       2020-02-18 15:36:43 +08:00
    @richard1122 也许是因为不能翻墙 8
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1401 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 23:43 · PVG 07:43 · LAX 15:43 · JFK 18:43
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.