问回溯的另一种选择

EN

是的，这个问题是有“解决方案”的，而且它们是大-大业务。解决好这个问题可以让你赚很多钱，因为它是NP难的，而且非常有用。http://en.wikipedia.org/wiki/Bin_packing_problem

我的第一个想法是用离散线性规划的方式重新表述问题，这已经完成了，如果你有访问权限，请参阅下面的参考。

Mhand，Imed Kacem，Stephane Negre，Lei Wu (2010)“三维装箱问题的线性规划方法”，离散数学电子笔记，36,993-1000

如果你还没有看过的话，我建议你看看动态编程的方法。你的问题听起来类似于“裁布”问题，这是一个典型的动态规划问题。下面是裁剪布料的问题：

裁剪布料。您将看到一块尺寸为X、Y的长方形布料，其中X和Y是正整数，以及可以使用该布料制作的n种产品的列表。对于每个产品i，1，1；n，你知道需要一块尺寸为ai，bi的长方形布料，产品的最终售价是ci。假设ai、bi和ci都是正整数。你有一台机器，它可以把任何一块长方形的布料水平或垂直地分成两块。设计一种算法来确定X，Y块布料的最佳回报，也就是说，裁剪布料的策略是由生成的布料制成的产品提供最大的销售价格总和。您可以随意复制给定产品的任意多个副本，如果需要，也可以不复制。

以下是我将如何将裁剪布料问题划分为子问题：

V( i,j) = max { V(i - ai, j- bi ) + ci,
                V(i - bi, j - ai ) + ci
              }