我使用最佳拟合方法为装箱问题编写了一个启发式算法，itens S =（i1，...，in），箱大小 T，并且想要创建一个真正的精确指数算法，以计算最佳解决方案（最小包装所有物品的箱子数量），但我不知道如何检查包装的每一种可能性，我在 C 中做。
有人可以告诉我任何想法我必须使用哪些结构？我怎样才能测试itens的所有de组合？它必须是递归算法吗？有一些可以帮助我的书或文章吗？
对不起，我的英语不好
问问题
2505 次
1 回答
0
给出的算法会找到一种包装，通常是一种非常好的包装，但不一定是最优的，所以它不能解决问题。
对于 NP 完全问题，解决它们的算法通常最容易递归地描述（迭代描述最终会明确所有被递归隐藏的簿记）。对于 bin 打包，您可以从最小数量的 bin 开始（对象大小总和除以 bin 大小的上高斯，但您甚至可以从 1 开始），尝试将对象分配到 bin 的所有组合，检查每个这样的分配它是合法的（bin 内容大小的总和 <= 每个 bin 的 bin 大小），如果是则返回接受（或输出找到的分配），或者如果没有找到分配，则增加 bin 的数量。
您要求结构，这是一个想法：每个 bin 应该以某种方式描述包含的对象（列表或数组），并且您需要所有 bin 的列表（或数组）。使用这些相当简单的结构，递归算法如下所示： 要尝试所有可能的分配，您为每个对象运行一个循环，该循环将尝试将其分配给每个可用的 bin。在检查合法性之前等待分配所有对象，或者（作为次要优化）在继续下一个对象之前只将一个对象分配给它适合的箱（这是在最后一个对象已经结束时结束的递归）已分配），如果没有找到这样的 bin，则返回前一个对象，或者（对于第一个对象）在重试之前增加 bin 的数量。
希望这可以帮助。
于 2013-03-27T14:49:42.300 回答