昨晚我正在开发一个应用程序，遇到了一个特定的问题，我确信可能有一个有效的算法来解决它。有人可以建议吗？
Problem:
TL;DR：也许一张图片会有所帮助：http://www.custom-foam-inserts.com/ http://www.custom-foam-inserts.com/。我有很多物品可以放在不同的隔间中：我想尽量减少需要携带的箱子数量。
.
我有一套N件昂贵的电子设备，我想将它们装入专门设计的保护盒中。这些盒子每个都有许多隔间，每个隔间可以容纳一个物品：其中一些专门设计用于容纳特定物品（即相机形状的孔），而其中一些是通用的（矩形孔）。我事先知道有 C 个不同尺寸的隔间以及这些尺寸是多少。
这些盒子有 L 种不同的布局，每个布局至少有一个隔间。布局可能是“两个大的矩形隔间和 4 个小的圆形隔间”。
每个隔间尺寸至少出现在一种布局上，但我有不适合任何隔间尺寸的物品。每件物品至少适合一个隔层，并且可以适合多个不同的隔层：例如，我的数码单反相机可能紧密适合“中矩形”隔层，宽松适合“大矩形”隔层，完美适合“大矩形”隔层。单反相机隔层”，但不适合“小圆圈”。为此，我列出了适合每件物品的隔间。
这些商品具有一定程度的异质性，例如可能有 50 个某种尺寸的商品和 20 个另一种尺寸的商品。
每个盒子有两个成本：体积和美元（但 D ~ 与 V 成比例）。我需要最大限度地减少其中一项或两项成本，同时将我的所有物品装入盒子中。由于盒子的布局，最佳解决方案可能包含未使用的隔间。如果两种溶液具有相同的体积，请选择具有最多未使用隔室的一种。由于每个隔间至少有一种布局，并且每个物品至少适合一个隔间，因此总有一种适合所有物品的解决方案。
项目数量：
对这个有什么想法吗？我研究了一些背包和装箱算法，但我不确定它们是正确的方法。非常感谢帮助。
从问题描述来看，这确实似乎是背包问题，因为您必须最大化可用空间，同时牢记weight您的选择。
根据您的需求，您还可以考虑使用遗传算法 http://en.wikipedia.org/wiki/Genetic_algorithm。由于这个问题是 NP Complete，如果您需要添加更多项目，运行时间最终会爆炸，所以如果我需要可用的最佳解决方案，而与所需的时间无关，我会主要使用这个。
另一方面，遗传算法应该能够在相对较短的时间内提供一些解决方案，但是它提供的解决方案可能不如背包算法提供的解决方案，所以我会选择遗传算法如果我的时间有限制，我需要提供一些解决方案，并且我不在乎它是否不是绝对最好的。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
