打包算法

Question

我有一组项目，以及相关的属性(重量、长度、宽度)。我还有一组包装类型，以及相关的属性(最大重量、长度、宽度)

我正在寻找一种算法，以确定最小数量的盒子包装的项目。

到目前为止，我已经探索了背包问题，尽管它可能很接近，但我并不完全是在处理权重、值类型的问题。

下面是一个例子：

物品: 10 x物品#1，(每个1磅，24“长，12”宽)5 x物品#2，(每个2磅，24“长，6”宽)

包装类型:小盒(MaxWeight =40磅，24"x12")大盒(MaxWeight =75磅，24"x24")

可能的打包方式是:2个小盒子，每个项目类型一个->，1个大盒子->里面的所有东西

我想要返回单个框的结果，尽管如果我可以返回所有可能的组合，那也可以。

Answer 1

你描述的是bin packing。请注意，这个问题是NP难的，因此如果不进行bruce力检查，您将无法获得最优解。也就是说，有一些算法可以给你一个足够好的答案。

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

Answer 2

这里有一个关于3D knapsack problem的有趣讨论。这里有一个关于同一主题的paper。

在类似的question之后也有类似的讨论。