假设有一个体积为“V”的容器。这个容器需要装入不同类型的箱子,每种箱子都有独特的体积大小,例如
箱子类型A – 体积为K箱子类型B – 体积为L
现在的问题是,需要找出这两种箱子可以装进容器的最大数量(两种箱子的组合)。
为了简化,让我们假设“W”和“R”是数量,那么我们得到(K * W) + (L * R) = V
并且需要确定这些箱子(纸箱)在容器中的堆放方式。
例如,容器中第一排箱子(这里的“排”是指箱子按x坐标排列)应该包含4叠(从容器底部开始)的“箱子类型A”,而最上面的两叠(靠近容器顶部)是“箱子类型B”(这里的“叠”是指箱子按z坐标堆叠)。之后,在前一排完成后继续铺设新的一排,直到整个容器装满。
问题在于如何在容器中最佳布局这些箱子,以利用容器内的所有(或大部分)空间,并尽可能多地装入箱子,这些箱子可以是1种或多种(每种容器最多约5种箱子)的组合。
程序应该简单地接受箱子类型和细节、容器的输入,然后就能得到一个完整的详细分析。
问题是我从未接触过机器学习或解决这类问题。如果能得到关于使用哪些算法、从哪里开始学习解决这个问题、如何最佳地处理这个问题、使用哪些有帮助的机器学习库等方面的建议,我将不胜感激。
回答:
这个问题是线性优化的一种变体,称为整数线性优化,维基百科链接。一般来说,这个问题被认为是NP难题,因此大多数解决方案都是迭代的。请参阅文章中的参考资料以获取进一步的讨论
编辑:我建议查看LPSOLVE,它已经提供了一个lgpl求解器库