这是一个创建于 2590 天前的主题，其中的信息可能已经有所发展或是发生改变。
问题是一个二维背包问题，但不是求二维背包的最优解。
问题是这样的，有多个背包和物品，每个物品有重量和体积两个维度，一个背包能够承受的重量和体积是有限的，问题就是判断所有的背包能不能背完所有的物品。
用二元组来描述背包和物品的重量和体积，比如 背包 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)；利用这种想法就产生错误的答案。。。
请问大大们有没有高效的解法？还是必须要暴力搜索才能解决问题？暴力搜索的思路是啥？
最后：大家节日快乐！
 |
1
holyghost 2017-10-24 11:26:52 +08:00
从一维背包判定能否装完引伸过来的一个想法：
如果二维背包 DP 的最优解和物品的总重量相同，是不是物品可以装完的充分必要条件？ |
 |
3
daozhihun 2017-10-24 20:03:00 +08:00  1
多背包问题目前好像没有高效的最优解法，是一个 NP 难的问题，不能在多项式时间出最优解（多个维度的话，状态转移方程多加一维就行了，但是多个背包不行），只能采取近似的方法。
楼主可以参考一下这个： http://www.cnblogs.com/jiaorenyu/p/multibags.html |
Select Language