java - 这是什么算法？盒装/背包？

Question

我昨晚在开发一个应用程序时遇到了一个特定的问题，我确信它可能有一个有效的算法来解决它。谁能推荐一下？

问题:

TL;DR:也许图片会有所帮助:http://www.custom-foam-inserts.com/ .我有很多元素可以放入不同的隔间:我想尽量减少我需要携带的箱子数量。

.

我有一套 N 件昂贵的电子设备，我想将它们装入专门设计的保护盒中。这些盒子每个都有许多隔间，每个隔间都可以装一件元素:其中一些是专门为装一件特定元素而设计的(即相机形状的孔)，还有一些是通用的(矩形孔)。我事先知道有 C 个不同尺寸的隔间以及它们的尺寸。

这些盒子有 L 种不同的布局，每种布局至少有一个隔间。布局可能是“两个大矩形隔间和 4 个小圆形隔间”。

每个隔间尺寸至少出现在一个布局中，但我有不适合任何隔间尺寸的元素。每件元素至少适合一个隔间，也可能适合多个不同的隔间:例如，我的 DSLR 相机可能适合放在“中长方形”隔间中，适合放在“大长方形”隔间中，适合放在“大长方形”中DSLR 相机隔层”，但不适合“小圆圈”。为此，我列出了适合每件元素的隔间。

商品中等程度的异质性——例如，可能有 50 件商品是一种尺寸，20 件商品是另一种尺寸。

每个盒子有两个成本 Volume 和 Dollars(但是 D ~ 与 V 成比例)。我需要将其中一项或两项成本降至最低，同时将我所有的元素都装进盒子里。由于盒子的布局，最佳解决方案可能包含未使用的隔间。如果两种解决方案的体积相等，请选择未使用隔间最多的一种。因为每个隔间至少出现在一个布局上，并且每个项目都适合至少一个隔间，所以总有一个适合所有项目的解决方案。

元素数量:<=2000，平均个案 150。隔间数量:<= 1000。布局数量:<= 1000。

对此有什么想法吗？我看过一些 Knapsack 和 Bin Packing 算法，但我不确定它们是否可行。非常感谢帮助。

Answer 1

从问题描述来看，这确实似乎是背包问题，因为您必须最大限度地利用可用空间，同时牢记您的选择的重量。

根据您的需求，您还可以考虑使用 Genetic Algorithm .由于这个问题是 NP Complete，如果您需要添加更多项目，运行时间最终会激增，所以如果我需要最好的可用解决方案而不用花费时间，我会选择这个。

另一方面，遗传算法应该能够在相对较短的时间内提供一些解决方案，但是它提供的解决方案可能不如背包算法提供的解决方案，所以我会如果我需要提供一些解决方案的时间有限制，那么选择一个 GA，我不在乎它是否不是绝对最好的。