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

有点不太清楚 一般背包算法?

  •  
  •   zhangwugui · 2017-11-11 15:07:14 +08:00 · 3515 次点击
    这是一个创建于 2329 天前的主题,其中的信息可能已经有所发展或是发生改变。

    0-1 背包算法:每个物品只有一件,放入背包中; V(80), W(60) V(50), W(50) V(50), W(50) 总重量 100 按照贪心算法放第一个,但实际取第二,第三个为最优;

    一般背包算法:每个物品多件,放入背包中; V(80), W(60) V(50), W(50) V(50), W(50) 总重量 100 按照贪心算法也只能放第一个,同样也不适用贪心算法?

    问题:一般背包是说物品有多件还是一件物品,可以取部分?

    16 条回复    2017-11-21 11:37:15 +08:00
    DaCong
        1
    DaCong  
       2017-11-11 15:24:42 +08:00 via Android
    先回答问题,是指一个物品有多件
    如果楼主想要深入学习背包的话,我这里收集过一个比较好的讲解,楼主可以参考一下

    https://github.com/tianyicui/pack/blob/master/V2.pdf
    zhangwugui
        2
    zhangwugui  
    OP
       2017-11-11 15:30:09 +08:00
    @DaCong 嗯,好的。我记得贪心算法应该是可以适用于一般背包算法的呢。那按照上面的来说,贪心算法不适用么?我先去看看这个 PDF。
    zhangwugui
        3
    zhangwugui  
    OP
       2017-11-11 15:35:32 +08:00
    我是在学习贪心算法的时候,看到贪心算法适用一般背包问题,而没搞明白的。
    DaCong
        4
    DaCong  
       2017-11-11 15:41:49 +08:00
    @zhangwugui #2 你的一般背包问题的定义是怎样的?
    是不是"有 N 种物品和一个容量为 V 的背包。第 i 种物品最多有 M i 件可用,每件耗费的空间是 C i ,价值是 W i。"?
    如果是的话,那么很显然不能贪心,看 PDF 中的多重背包就可以了。
    DaCong
        5
    DaCong  
       2017-11-11 15:44:48 +08:00   ❤️ 1
    @zhangwugui #3 就看那个人对于一般背包的定义了,在我看来,背包问题,就要保证物品不可分割。如果所谓的“一般背包”是可以分割物品的,那就可以贪心(算单位体积的价值,取最大)。
    zqqian
        6
    zqqian  
       2017-11-11 15:47:52 +08:00 via Android
    可以去看看背包九讲
    zhangwugui
        7
    zhangwugui  
    OP
       2017-11-11 16:01:02 +08:00
    @DaCong 嗯,对于一般背包我是这样理解的:有 N 件物品和一个最大重量为 V 的背包,其中每件物品有多个,每件背包重量为 W(i),每件物品价值为 P(i),在保证不超过最大重量 V 的情况下,放入的物品价值最大?
    因为我现在学的贪心算法,也看了看网上说的,贪心算法可以解决这个问题,就使用贪心算法:
    依次取 价值除以重量 P(i)/W(i) 最大的放进去就行,但实际上这确实不行的。不知道这种情况算一般算法不,还是我说的这个贪心策略不对。
    DaCong
        8
    DaCong  
       2017-11-11 16:06:08 +08:00
    @zhangwugui #7 多个是指没有上限吗?如果是的话,就是完全背包问题,我给你的链接里有讲到
    我给你的 PDF 就是 6# 说的背包九讲
    zjsxwc
        9
    zjsxwc  
       2017-11-11 16:36:54 +08:00 via Android
    mark 下, 动态规划主要就是状态转移方程。

    我记得背包问题在那个讲解图里面:
    01 背包是 斜、 竖 方向的 转移
    完全背包是 横、 竖 方向的 转移
    xupefei
        10
    xupefei  
       2017-11-11 17:26:07 +08:00   ❤️ 1
    可以放无限次的叫 unbounded knapsack,放一次的叫 0/1 knapsack,可拆分的叫 fractional knapsack。
    没有“一般背包”这种说法。

    0/1 背包用贪心算法能保证 50%最优解。
    fractional knapsack 的贪心算法可以保证最优解:通过事先按照 value/weight 比值排序后逐个选取。
    xupefei
        11
    xupefei  
       2017-11-11 17:26:58 +08:00
    @xupefei #10 第一句写错了,每个条目最多放 N* 次,N*是常量。
    zhangwugui
        12
    zhangwugui  
    OP
       2017-11-11 18:01:33 +08:00
    @DaCong 嗯嗯,感谢。大概明白了,我可能太纠结在贪心算法了。去学习学习动态规划。
    zhangwugui
        13
    zhangwugui  
    OP
       2017-11-11 18:07:44 +08:00
    @xupefei 嗯,多谢指导,明白了。我所说的那种应该就是 unbounded knapsack。
    nicoley
        14
    nicoley  
       2017-11-11 23:32:41 +08:00
    @zjsxwc 动态规划我个人感觉它就三部曲,状态的定义,状态如何转移,再就是一些边界条件。。而不是你所说的主要是状态转移。。。。(个人愚见,请大家多多指教
    jedihy
        15
    jedihy  
       2017-11-12 08:24:09 +08:00
    @zhangwugui 面试极少会考到,不是个人兴趣没必要太深究了。
    zhangwugui
        16
    zhangwugui  
    OP
       2017-11-21 11:37:15 +08:00
    @jedihy 嗯,最近回过头来看算法的时候,又看到了,再了解下。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3861 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 05:09 · PVG 13:09 · LAX 22:09 · JFK 01:09
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.