计算最大包大小(以PHP为单位)

Question

为此使用PHP.

从给定的一组物品中,每个物品都有自己的重量,我需要自动计算将物品包装成100磅包装的最有效方法(最大包装重量100磅是静态的,但将来可以更改).单个包不能超过指定的最大值.

例如,我有5件物品 - 总重量为254磅:

人们会认为254磅需要3 x 100磅的包装.这个例子有意地证明了情况并非总是如此.某些项目配置无法很好地协同工作.此示例在其最佳配置中需要4 x 100 lbs的包.

项目数量和权重是完全可变的,没有单个项目将超过100磅.

实现这一目标的最佳方式是什么？

Answer 1

您描述的问题称为Bin装箱问题.没有人知道解决它的最佳方法.如果他们这样做,他们将能够证明P = NP或P!= NP - 计算中一个重要的开放性问题.

维基百科页面包括对一些示例算法的引用 - 第一拟合算法,最佳拟合递减,第一拟合递减.一般来说,解决这个问题的一种快速方法是不尝试找到最优解,而是找到一个好的近似值."减少"指的是首先包装最大,最笨拙的元素,然后用最后的小元素填充间隙是一个好主意.这实际上类似于大多数人通常如何处理这个问题.

对于您在示例中给出的问题的大小,仅通过检查所有可能的排列来找到最佳解决方案将很简单,但显然对于较大的示例而言效率不高.