这是什么算法？盒装/背包？ [英] What kind of algorithm is this? Box packing/Knapsack?

问题描述

昨晚我在开发一个应用程序时，遇到了一个特定的问题，我敢肯定它可能有一种有效的算法可以解决该问题。有人会建议吗？

I was working on an application last night and came across a particular problem which I'm sure probably has an efficient algorithm to solve it. Could anyone suggest?

问题：

TL; DR：也许图片会有所帮助： http://www.custom-foam-inserts.com/ 。我有很多物品适合各种隔间：我想尽量减少需要拿走的箱子数量。

TL;DR: Maybe a picture will help: http://www.custom-foam-inserts.com/ . I have lots of items which fit in a range of compartments: and I want to minimise the number of cases I need to take.

。

我有N套昂贵的电子设备，我想将它们包装到专门设计的保护盒中。这些盒子每个都有许多隔室，每个隔室都可以容纳一个物品：其中一些专门设计用于容纳特定物品（例如，照相机形孔），而另一些则是通用的（矩形孔）。我预先知道有C个不同大小的隔间，它们是什么大小。

I have a set of N items of expensive electronic equipment which I want to pack into specially designed protective boxes. These boxes each have many compartments which can each fit a single item: some of which are designed specially to fit a particular item (ie, a camera shaped hole) and some of which are generic (a rectangular hole). I know in advance that there are C different sizes of compartment and what sizes these are.

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

These boxes come in L different layouts, each with at least one compartment. A layout might be ‘two large rectangular compartments and 4 small circular compartments’.

每个隔间的大小至少出现在一个布局上，但是我有一些东西没有适合任何隔间尺寸。每个项目至少可容纳一个隔间，并可放入多个不同的隔间中：例如，我的DSLR相机可能紧紧套在中矩形隔间中，松散地插在大矩形中，而完美地适合于 DSLR相机舱，但不适合小圆圈。为此，我列出了适合每种物品的隔层。

Each compartment size is present on at least one layout, but I have items which don’t suit any compartment size. Each item fits at least one compartment and may fit into multiple different compartments: for example, my DSLR camera might be a tight fit in a ‘medium rectangle’ compartment, a loose fit in a ‘large rectangle’ and a perfect fit in a ‘DSLR camera compartment’, but won’t fit in a ‘small circle’. To this end I’ve made a list of which compartments are suitable for each item.

这些项目是中等异构的-例如，可能有一个大小的50个项目和另一个大小的20个项目。

The items are moderately heterogeneous – for example there may be 50 items of one size and 20 items of another size.

每个盒子有两个成本，数量和美元（但是D与V成正比）。在将我的所有物品都装进盒子里的同时，我需要将这些费用中的一项或两项减至最少。由于盒子的布局，最佳解决方案可能包含未使用的隔间。如果两种溶液的体积相等，请选择间隔最多的溶液。因为每个隔间都存在于至少一个布局上，并且每个项目都适合至少一个隔间，所以总有一种解决方案可以容纳所有项目。

Each box has two costs Volume and Dollars (however D ~proportional to V). I need to minimise one or both of these costs whilst fitting ALL of my items into the boxes. Due to the layouts of the boxes, the optimal solution may contain unused compartments. If two solutions have equal volume, select the one with the most unused compartments. Because each compartment is present on at least one layout and each item fits in at least one compartment, there is always a solution which fits all items.

项目数：< ; = 2000，平均情况为150。
隔间数：< =1000。
布局数：< = 1000。

Number of items: <=2000, average case 150. Number of compartments: <= 1000. Number of layouts: <= 1000.

任何关于这个的想法？我对背包和装箱算法有所了解，但不确定它们是否可行。

Any ideas on this one? I've looked a bit at Knapsack and Bin Packing algorithms and I'm not sure they're the way to go. Help much appreciated.

推荐答案

从问题描述来看，这似乎确实是背包问题，因为您必须在最大程度地利用可用空间的同时请记住您的选项的 weight 。

From the problem description this does indeed seem to be knapsack problem since you have to maximise your space available while keeping in mind the weight of your options.

根据您要执行的操作，您还可以考虑使用遗传算法。由于此问题是NP Complete，如果您需要添加更多项目，运行时间最终会激增，因此，如果我需要与时间无关的最佳解决方案，我会主要考虑这一点。

Depending on what you are after, you could also consider using a Genetic Algorithm. Since this problem is NP Complete the running time will eventually explode should you need to add more items, so I would go with this primarily if I need the best solution available irrelevant of the time it takes.

另一方面，遗传算法应该能够在相对较短的时间内提供一些解决方案，但是，它提供的解决方案可能不如Knapsack算法提供的解决方案好，因此，如果我在需要提供一些解决方案的时间上有限制，并且我不在乎它是否不是绝对的最佳选择，我会选择GA。

On the other hand, the Genetic Algorithm should be able to provide with some solution in a relatively small period of time, however, the solution it provides might not be as good as the one provided by the Knapsack algorithm, so I would choose a GA if I have restrictions on the time I need to provide some solution and I do not care if it is the not absolute best.

这篇关于这是什么算法？盒装/背包？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！