2

I've got a set of items, with associated attributes (Weight, Length, Width). I've also got a set of Packaging Types, with associated attributes (Max Weight, Length, Width)

I'm looking for an algorithm to determine the LEAST amount of boxes to package the items into.

So far, I've explored the knapsack problem, and although it can come close, I'm not exactly dealing with a weight, value type problem.

Here's an example:

Items: 10 x Item #1, (1lb each, 24" long, 12" wide) 5 x Item #2, (2lb each, 24" long, 6" wide)

Packaging Types: Small Box (MaxWeight = 40lbs, 24"x12") Large Box (MaxWeight = 75lbs, 24"x24")

The possible ways to package this would be: 2x Small Box -> One for each item type 1x Large Box -> Everything in it

I would want to return the single box result, although if I could return all possible combinations, that would also work.

4

2 回答 2

7

您正在描述装箱。请注意，这个问题是 NP 难题，因此如果没有强力检查，您将无法获得最佳解决方案。也就是说，IMO，有些算法可以为您提供足够好的答案。

搜索最佳拟合递减和首次拟合递减的描述。

于 2009-07-26T19:23:59.293 回答
1

这是一个关于3D 背包问题的有趣讨论。这是一篇关于同一主题的论文。

在类似的问题之后进行了类似的讨论。

于 2009-07-27T11:58:15.603 回答