好的，伙计们，我有一个现实世界的问题，我需要一些算法来解决这个问题。
我们有一堆订单等待发货，每个订单都有一个体积（以立方英尺为单位），比如说 V1、V2、V3、...、Vn
承运商可以为我们提供四种类型的集装箱，集装箱的数量/价格如下：
容器类型 1：2700 立方英尺/2500 美元；
容器类型 2：2350 立方英尺/2200 美元；
集装箱类型 3：2050 立方英尺/2170 美元；
集装箱类型 4：1000 立方英尺/1700 美元；
没有一个订单会超过 2700 CuFt，但可能会超过 1000 CuFt。
现在我们需要一个程序来获得运费的优化解决方案，即最低价格。
我感谢任何建议/想法。
编辑：
我目前的实现是首先使用最大的容器，对装箱应用第一个适合减少算法以获得结果，然后解析所有容器并根据内容量调整容器大小......
我在一家物流公司工作时写了一个类似的程序。这是一个 3 维装箱问题，比经典的 1 维装箱问题要棘手一些——我工作中编写我要替换的旧装箱程序的人犯了一个错误，即减少所有内容到一维装箱问题（盒子的体积和包裹的体积），但这不起作用：这个问题公式表明三个 8x8x8 的包裹可以装进一个 12x12x12 的盒子，但这会让你有重叠的包裹。
我的解决方案是使用所谓的断头台切割启发法：当您将包裹放入运输容器时，这会产生三个新的空子容器：假设您将包裹放在容器的左下角，那么您将拥有包前面的空间有一个新的空子容器，包右边的空间有一个新的空子容器，包顶部的空间有一个新的空子容器。一定不要为多个子容器分配相同的空白空间，例如，如果您不小心，则将容器右前部的部分分配给前子容器和右侧子容器，您只需要选择一个来分配它。这种启发式将排除一些最佳解决方案，但速度很快。（作为一个具体的例子，假设您有一个 12x12x12 的盒子，然后将一个 8x8x8 的包装放入其中 - 这将留下一个 4x12x12 的空子容器、一个 4x8x12 的空子容器和一个 4x8x8 的空子容器。请注意，分配可用空间的错误方法是拥有三个 4x12x12 空子容器 - 这将导致包重叠。如果盒子或包裹不是立方体，那么您将有不止一种方法来划分可用空间 - 您需要决定是最大化一个或两个子容器的大小，还是尝试创建三个或多或少相等的子容器。）您需要使用合理的标准来订购/选择子容器，否则子容器的数量将成倍增长；我通过首先填充最小的子容器并移除任何太小而无法容纳包裹的子容器来解决这个问题，从而将子容器的数量保持在合理的数量。
您有几个选项：使用什么容器，如何旋转进入容器的包裹（通常有六种旋转包裹的方法，但并非所有旋转对于某些包裹都是合法的，例如“this end up”包裹将只有两个旋转），如何划分子容器（例如，您将重叠空间分配给正确的子容器还是分配给前面的子容器），以及您以什么顺序包装容器。我使用了一种随机算法，该算法近似于最佳拟合递减启发式（使用体积作为启发式），并且倾向于创建一个大型子容器和两个小型子容器，而不是三个中型子容器，但我使用了随机数字生成器来混合（所以最大的可能性是我会先选择最大的包，但是我首先选择第二大包裹的可能性较小，依此类推，而我首先选择最小包裹的可能性最低；同样，我有可能更喜欢创建三个中型子容器而不是一个大两个小，有可能我会使用三个中型盒子而不是两个大盒子，等等）。然后我并行运行了几十次，并选择了成本最低的结果。d 使用三个中型盒子而不是两个大盒子等）。然后我并行运行了几十次，并选择了成本最低的结果。d 使用三个中型盒子而不是两个大盒子等）。然后我并行运行了几十次，并选择了成本最低的结果。
我考虑了其他启发式方法，例如极值启发式方法较慢（虽然仍在多项式时间内运行 - IIRC 它是一个三次时间解决方案，而断头台切割启发式方法是线性时间，而在另一个极端，分支定界算法发现最优解并在指数时间内运行）但更准确（具体来说，它会找到一些被断头台切割启发式排除的最优解）；然而，我的用例是我应该产生一个快速的运输估计，所以极点启发式是不合适的（它太慢而且“太准确”——我需要增加 10% 或 20 % 以说明实际包装盒子的人不可避免地会做出次优选择）。
我不知道程序的名称，但可能有一些商业软件可以为你解决这个问题，这取决于一个好的解决方案对你来说价值多少。
Zim Zam 的答案适用于大盒子，但假设相对较小的盒子，您可以使用更简单的算法，该算法相当于求解带约束的积分线性方程：
其中 a、b、c 和 d 是整数，表示使用的每种容器的数量：
鉴于，
2700a + 2350b + 2050c + 1000d <= V（其中 V 是订单总量）
您希望找到 a、b、c 和 d 以使以下函数最小化：
总成本 C = 2500a + 2200b + 2170c + 1700d
看来您可以蛮力解决这个问题（这很难解决）。计算 a、b、c 和 d 的每个可能的可行组合，并计算每个组合的总成本。请注意，任何解决方案都不会使用超过 1 个 d 类型的容器，因此会减少可能组合的数量。
我假设订单可以在容器之间拆分。