集装箱最大化装载量问题？

业务中有个功能，计算N个M种规格集装箱中装载F种尺寸的D个货品的最大化装载方法。 举例，有5种货品，每种货品的数量分别是200，300，400，100，800。这5种货品的长宽高不相同。 现在有3种规格的集装箱，现在希望最大化利用集装箱的容量装载这些货品。 看看大家有什么好的算法。

这个集装箱题目标一般模子是 3BKP —— Three Dimensional Bounded Knapsack Problem (with Balancing) 。给定一个三维立方体空间，以及多少三维立方体物品（和它们的质量），要求最大化操纵空间（大概斟酌物品的代价），而且还要求重心只管平衡。

论文：https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2011-51.pdf

和普通的“多维背包”纷歧样——多维背包里每个维度是互不相关的（e.g. 体积 & 重量），而不是一个“立方体”的长宽高三维。而且还多了一个物体朝向（扭转）的题目。直觉上应当更难，八成也是 NP-Hard 的。

要求不高（包括数据范围不大、或不要求最优解）的话，前者可以暴力搜索，后者可以随机化大概贪心试试看。那篇论文里就给了一个非最优的启发式解。

Knapsack problem, 背包问题
问题本身是NP-hard, 有DP的多项式复杂度算法，看wiki