装箱-精确np-hard指数算法

Question

我写了一个启发式算法为装箱问题使用最佳拟合方法，itens S=(i1，...，in)，箱大小T，并希望创建一个真正的精确指数算法，它计算最优解(最小数量的箱来包装所有的iten)，但我不知道如何检查每种可能的包装，我在C中做。

有人能告诉我我必须使用什么结构吗？如何测试itens的所有解组合？它必须是一个递归算法？有没有可能对我有帮助的书和文章？

对不起，我的英语不好

Answer 1

给出的算法会找到一种填充，通常是相当好的，但不一定是最优的，所以它不能解决问题。

对于NP完全问题，解决它们的算法通常是最容易递归描述的(迭代描述大多最终使递归隐藏的所有记账变得明确)。对于存储箱打包，您可以从最小数量的存储箱开始(对象大小总和除以存储箱大小的高斯值，但您甚至可以从1开始)，尝试将对象分配到存储箱的所有组合，检查每个此类分配是否合法(每个存储箱的存储箱内容大小和<=存储箱大小)，如果合法，则返回接受(或输出找到的分配)，或者如果未找到分配，则增加存储箱的数量。

你需要结构，这里有一个想法:每个bin应该以某种方式描述所包含的对象(列表或数组)，而您需要所有bin的列表(或数组)。有了这些相当简单的结构，递归算法看起来像这样:为了尝试所有可能的赋值，您为每个对象运行一个循环，该对象将尝试将其赋值给每个可用的bin。要么在检查合法性之前等待所有对象都被分配，要么(作为一个小优化)在继续下一个对象(这是当最后一个对象被分配时结束的递归)之前只将一个对象分配给它适合的bin，如果找不到这样的bin，则返回到前一个对象，或者(对于第一个对象)在重试之前增加bin的数量。

希望这能有所帮助。