包装物品放入垃圾箱的固定号码 [英] Packing items into fixed number of bins

问题描述

我在寻找一种算法，能解决我的问题，最有效的方式。

I am looking for an algorithm that will solve my problem in the most efficient way.

问题描述：

予有项目的列表（只有正整数被允许）以及相同容量仓固定数目。到目前为止，我想到了分支定界算法，但我不能肯定，如果它是在这种情况下，最好的办法。

I have a list of items (only positive integers are allowed) and fixed number of bins of identical capacity. So far, I thought about branch-and-bound algorithm, but I am not quite sure if it is the best approach in this case.

示例：

由于项目的列表：

(3, 4, 4, 2, 3, 9, 2)

和能力9每三个垃圾桶 我要收拾他们：（订单的产品无关）

and three bins of capacity 9 each I need to pack them this: (order of items is irrelevant)

[3, 4, 2], [4, 3, 2], [9]

我觉得这是（我知道是NP完全性）的装箱问题的一个变种，但因为我不是试图尽量减少使用箱的号码，我不知道是否有更好的解决方案。

I think this is a variant of the bin-packing problem (which I know is NP-complete), but since I am not trying to minimize number of bins used I wonder if there is a better solution.

推荐答案

这是多纸盒包装问题：

给定一组项目，每一个特定尺寸的，和一组仓中，每个   一个特定的大小，以及 - 是那里的物品到垃圾箱分布   这样没有项目在无包装，无纸槽容量超过？

Given a set of items, each of a specific size, and a set of bins, each of a specific size as well – is there a distribution of items to bins such that no item is left unpacked and no bin capacity is exceeded?

在总体上是一个NP难。然而，也有可能有效地解决了一些特殊情况下，或者大约或甚至最佳状态。

In general it is NP-hard. However, there are several special cases that may be solved efficiently, either approximately or even optimally.

看沃尔夫冈的Stille AUSGöppingen的论文

这篇关于包装物品放入垃圾箱的固定号码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！