装箱动态规划问题 [英] Bin Packing Dynamic Programming Question

问题描述

您有尺寸S1的N1项目，规模S2的N2项目，规模S3的N3项目。您想包所有这些项目到每个容C的垃圾箱，使得回收箱所使用的总数量最小化

You have n1 items of size s1, n2 items of size s2, and n3 items of size s3. You'd like to pack all of these items into bins each of capacity C, such that the total number of bins used is minimized.

如何才能实现用箱的最低数量的解决方案？贪婪是不一定的工作。

How can we achieve a solution using minimum number of bins? Greedy isn't surely working.

推荐答案

这不是一个愚蠢的问题，海事组织。

It is not a dumb question, IMO.

装箱，一般被称为是NP完全问题。

Bin packing in general is known to be NP-Complete.

不过你的情况，有斌物体重量的固定数量的包装是一个有趣的变种。

But your case, Bin packing with fixed number of object weights is an interesting variant.

下面的文章声称有一个多项式时间算法自带withing 1最优的：<一href="http://linkinghub.elsevier.com/retrieve/pii/S0377221706004310">http://linkinghub.elsevier.com/retrieve/pii/S0377221706004310当你让3种不同尺寸。 （警告：我只是由抽象去）

The following paper claims to have a polynomial time algorithm which comes withing 1 of optimal: http://linkinghub.elsevier.com/retrieve/pii/S0377221706004310 when you allow 3 different sizes. (Caveat: I am only going by the abstract).

所以我猜这个版本是一个NP难也和贪心算法将可能无法正常工作。不太确定动态规划（装箱是强NP完全的）。

So I am guessing this version is NP-Hard too and Greedy algorithm will likely not work. Not so sure of dynamic programming (bin packing is strongly NP-Complete).

希望有所帮助。

这篇关于装箱动态规划问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！