M**********7
发帖数: 378 | 1 有N个物品放在M个背包里面。
背包有容积和承重限制。
物品有体积和重量。
求重新整理背包，让M个背包的容积和承重都尽量平均，物品移动数量尽量少。
显然是NP所以不要求最优解，但结果也不能太挫了，要求时间复杂度尽可能小。 |
l*****z
发帖数: 3022 | 2 给个想法，
扫描一遍找到总重量处以M得到每个包的最佳重量，再按重量排序，然后从最重的报开
始往最轻的移动物品，移动到差不多最佳就下一个包，2个指针往中间移动。
【在 M**********7 的大作中提到】
: 有N个物品放在M个背包里面。
: 背包有容积和承重限制。
: 物品有体积和重量。
: 求重新整理背包，让M个背包的容积和承重都尽量平均，物品移动数量尽量少。
: 显然是NP所以不要求最优解，但结果也不能太挫了，要求时间复杂度尽可能小。
|
M**********7
发帖数: 378 | 3 嗯，感觉方向对。
如何同时考虑重量和体积限制呢？
【在 l*****z 的大作中提到】
: 给个想法，
: 扫描一遍找到总重量处以M得到每个包的最佳重量，再按重量排序，然后从最重的报开
: 始往最轻的移动物品，移动到差不多最佳就下一个包，2个指针往中间移动。
|
l*****z
发帖数: 3022 | 4 看错了，以为只要最优化重量。。。看来不work，汗
【在 M**********7 的大作中提到】
: 嗯，感觉方向对。
: 如何同时考虑重量和体积限制呢？
|
l*****z
发帖数: 3022 | 5 可以先只管重量优化一次，如何再按体积来一次。
算是greedy吧。不知道行不行。。。
【在 M**********7 的大作中提到】
: 嗯，感觉方向对。
: 如何同时考虑重量和体积限制呢？
|
M**********7
发帖数: 378 | 6 能不能具体说说怎么叠加两次的结果？
【在 l*****z 的大作中提到】
: 可以先只管重量优化一次，如何再按体积来一次。
: 算是greedy吧。不知道行不行。。。
|
l*****z
发帖数: 3022 | 7 就是简单粗暴的先优化重量，在优化后的结果上优化大小，不过肯定不是最优
【在 M**********7 的大作中提到】
: 能不能具体说说怎么叠加两次的结果？
|
M**********7
发帖数: 378 | 8 明白了， 是不是 优化重量的时候如果体积不合适就放弃，之后优化体积的时候也一样。
想不好如何避免在优化体积的时候同时不把重量的优化全都丢掉。
可不可以利用密度?
【在 l*****z 的大作中提到】
: 就是简单粗暴的先优化重量，在优化后的结果上优化大小，不过肯定不是最优
|
l*****z
发帖数: 3022 | 9 是的。
密度是个有意思的想法，呵呵
样。
【在 M**********7 的大作中提到】
: 明白了， 是不是 优化重量的时候如果体积不合适就放弃，之后优化体积的时候也一样。
: 想不好如何避免在优化体积的时候同时不把重量的优化全都丢掉。
: 可不可以利用密度?
|
l******s
发帖数: 3045 | 10 背包和物品的重量和体积都分别相同么？还是不同？
还有就是“尽量平均“怎么定义？重量平均优先还是体积平均优先？这两个有可能矛盾。 |
M**********7
发帖数: 378 | 11 可以不同。
尽量平均是由人来判定差不多就可以，
具体的定义可以自己定义，说是可以用最大减最小的百分比，或者用比例的标准差，或
者任何觉得合适的，甚至没有都可以，只要算法能达到一个合理的结果就可以。
重量和体积的地位是均等的，矛盾的时候兼顾，最后的结果不需要每项最优，足够好就
好。
盾。
【在 l******s 的大作中提到】
: 背包和物品的重量和体积都分别相同么？还是不同？
: 还有就是“尽量平均“怎么定义？重量平均优先还是体积平均优先？这两个有可能矛盾。
|
