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

一个二维背包问题,求对算法有研究的大大解答

  •  
  •   whutgeek · 2017-10-24 11:02:26 +08:00 · 4714 次点击
    这是一个创建于 2571 天前的主题,其中的信息可能已经有所发展或是发生改变。

    问题是一个二维背包问题,但不是求二维背包的最优解

    问题是这样的,有多个背包和物品,每个物品有重量和体积两个维度,一个背包能够承受的重量和体积是有限的,问题就是判断所有的背包能不能背完所有的物品

    用二元组来描述背包和物品的重量和体积,比如 背包 1=(3,3),背包 2=(7,7),物品 1=(4,4),物品 2=(4,4),背包不能背完所有物品;但是假如 物品 1=(2,3),物品 2=(6,7) 就可以背完所有物品。

    PS:自己有这样想过:对每一个背包求解二维背包问题,目的是尽量多地背更多的物品(这样可以用 DP ),可以得到每个背包背的物品数目的最优解;比如背包 1 求解得到背包 1 背的物品的最优解集 C1,背包 2 求解得到背包 2 背的物品的最优解集 C2...最后对这些解集求并集:C1 U C2 U ... ,如果并集可以得到整个物品,那就可以背完;但是这样每个背包就只会倾向于背重量和体积最小的物品,导致所有的背包都不会选择背大物品,最后导致失败。。比如背包 1=(3,3),背包 2=(3,3);物品 1=(1,1),物品 2=(1,1),物品 3=(2,2);利用这种想法就产生错误的答案。。。

    请问大大们有没有高效的解法?还是必须要暴力搜索才能解决问题?暴力搜索的思路是啥?

    最后:大家节日快乐!

    4 条回复    2017-10-24 21:45:57 +08:00
    holyghost
        1
    holyghost  
       2017-10-24 11:26:52 +08:00
    从一维背包判定能否装完引伸过来的一个想法:
    如果二维背包 DP 的最优解和物品的总重量相同,是不是物品可以装完的充分必要条件?
    whutgeek
        2
    whutgeek  
    OP
       2017-10-24 11:37:23 +08:00
    @holyghost 谢谢回复!不过我在后面的 PS 中已经说了,不行呀,有反例的
    daozhihun
        3
    daozhihun  
       2017-10-24 20:03:00 +08:00   ❤️ 1
    多背包问题目前好像没有高效的最优解法,是一个 NP 难的问题,不能在多项式时间出最优解(多个维度的话,状态转移方程多加一维就行了,但是多个背包不行),只能采取近似的方法。

    楼主可以参考一下这个: http://www.cnblogs.com/jiaorenyu/p/multibags.html
    whutgeek
        4
    whutgeek  
    OP
       2017-10-24 21:45:57 +08:00
    @daozhihun 嗯嗯,我也觉得这个问题应该是属于 NP hard 的了。。。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3076 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 13:17 · PVG 21:17 · LAX 05:17 · JFK 08:17
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.