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

[whutgeek]

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

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

用二元组来描述背包和物品的重量和体积，比如 背包 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)；利用这种想法就产生错误的答案。。。

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

最后：大家节日快乐！

[holyghost]

从一维背包判定能否装完引伸过来的一个想法：
如果二维背包 DP 的最优解和物品的总重量相同，是不是物品可以装完的充分必要条件？

[whutgeek]

@holyghost 谢谢回复！不过我在后面的 PS 中已经说了，不行呀，有反例的

[daozhihun]

多背包问题目前好像没有高效的最优解法，是一个 NP 难的问题，不能在多项式时间出最优解（多个维度的话，状态转移方程多加一维就行了，但是多个背包不行），只能采取近似的方法。

楼主可以参考一下这个： http://www.cnblogs.com/jiaorenyu/p/multibags.html

[whutgeek]

@daozhihun 嗯嗯，我也觉得这个问题应该是属于 NP hard 的了。。。