问题是一个二维背包问题,但不是求二维背包的最优解。
问题是这样的,有多个背包和物品,每个物品有重量和体积两个维度,一个背包能够承受的重量和体积是有限的,问题就是判断所有的背包能不能背完所有的物品。
用二元组来描述背包和物品的重量和体积,比如 背包 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 |