问题是我有 X 个不同权重值的物品必须放入 Y 个容器中。容器具有不同的尺寸(例如容纳不同的最大重量)。每个集装箱的总装载量必须大致等于其他集装箱的装载量,但集装箱不需要装满或最小化。必须使用所有容器。
这让我想起了“背包”问题,但是我有多个不同尺寸的背包,它们之间的负载必须相对相等(例如一个背包只能容纳12磅,另一个背包只能容纳8磅,但它们都需要填充其可承载总重量的相同百分比)。它还让我想起了“垃圾箱包装”问题,但这并不涉及不同的垃圾箱大小,或者垃圾箱不需要装满或最小化,它们只需要等效的负载,并且所有这些都需要使用。
谁能指出我在数据结构和算法理论中这个问题的名称的正确方向?我还对可能常用于解决此类问题的任何算法或启发式方法或有关可能的时间复杂度的信息感兴趣。
对我来说听起来像是多个背包。从维基百科 http://en.wikipedia.org/wiki/List_of_knapsack_problems:
如果我们有 n 个物品和 m 个容量为 Wi 的背包,我们就会遇到多背包问题
编辑:抱歉,错过了有关每个容器需要类似加载的信息。尽管如此,它smells就像多个背包一样,尽管有额外的限制。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)