资 源 简 介
装箱问题
在装箱问题，对象不同的卷必须挤进有限数量的桶或容器每个的第五卷中将使用的回收箱的数目降至最低的方式。在计算复杂性理论，它是一个组合的 NP 难问题。
还有很多变化的这个问题，如 2D 包装、 线性包装，包装的重量、 包装成本，等等。他们有许多应用程序，例如填满的容器，载货汽车与重量的能力制约，在可移动媒体和现场可编程门阵列半导体芯片设计中的技术映射创建文件备份。
装箱问题也可以被视为下料问题的一个特殊情况。当回收箱的数目只限于 1 和每个项目描绘为一个卷和一个值时，可以适合在箱子里的物品价值最大化的问题被称为背包问题。
尽管装箱问题有 NP 难的计算复杂性，以复杂的算法可生产非常大量的实例问题的最优解。此外，已制定了很多启发式算法： 例如，第一个适合的算法中，提供一个快速但往往非最优解决方案，涉及将每个项放入第一次的 bin 在其中它会适合。它需要 Θ (n) 的时间，其中 n 是要将打包的元素数。通过第一次排序到递减顺序排列 （有时称为第一合适降低算法），虽然这仍然不能保证最佳的解决方案，但和更长的列表的元素的列表可能会增加运行时间的算法，可以作算法有效得多。然而，众所周知总是存在至少一个排序的项目，允许第一个适合以产生最佳的解决方案。[] 1
装箱在实践中出现的一个有趣的变形时，项目可以共享空间，当挤进垃圾桶。具体来说，一组项可以占用较少空间时挤在一起比其个体大小的总和。这个变形被称为 VM 包装 [2]，因为当虚拟机 (Vm) 包装在服务器中，其总的内存需求可能减少由只需要一次存储的虚拟机共享的页面。如果项目可以以任意方式共享空间，装箱问题很难甚至近似。但是，如果作为分享到层次结构中，适合的空间是在虚拟机中共享内存的情况，装箱问题可以高效地接近。
