装箱：最大化垃圾箱数量/“Fukubukuro”问题？

计算科学 优化 算法 近似
2021-12-20 16:40:02

我最近遇到了一个看起来像是垃圾箱包装或背包问题的变体的问题，但目标是最大化垃圾箱/背包的数量：

考虑有一个M项列表，分别具有正值v 1到v M。还有一个标准尺寸的垃圾箱，最多可装载C件物品。目标是将项目分配到尽可能多的箱中，每个箱的总值至少为V。问题是，给定v 1 .. v M、C和V，如何获得最大可能的填充箱数？和实际的模式？

我实际的现实生活问题实际上更难了一步。除了(A)最多填写C项总价值至少为V之外，还有一种选择(B)最多填写C项总价值至少为2* V。这两种垃圾箱都可以生产任意次数，但第二种垃圾箱（自动）价值是第一种垃圾箱的两倍。那么问题是，垃圾箱的最大可能价值是多少，即

1 * number of type (A) bins + 2 * number of type (B) bins,

和实际的模式？

我只是为我如何想象它与背包问题的区别而编造了“ fukubukuro问题”这个名称 :) 我还不知道这个问题的实际名称，所以如果有人能给出一个方向，我很感激。我也猜想这可以通过整数线性规划来解决，但我希望学习任何更具体的算法或近似值。

2个回答

我发现了 Boyar 等人的一篇论文（大约 2005 年），该论文研究了此类问题的算法，他们称之为最大资源装箱问题（与装箱以最小化资源（例如垃圾箱）。

通常，对于装箱问题，我们会尽量减少使用的箱数，或者在双箱装箱问题的情况下，最大化接受物品的数量或总尺寸。本文介绍了相反问题的结果，我们希望最大化使用的 bin 数量或最小化接受项目的数量或总大小。我们考虑问题的离线和在线变体。

在线变体是指在进行下一个项目之前必须将“当前项目”分配到箱中的问题，而离线变体允许选择要分配的项目而不考虑这种输入顺序。

通过将最优解 OPT(I)（使用的最大箱数）与线性函数绑定来评估算法的性能CALG(一) +b算法使用的数量，并定义近似比率R一个大号G成为C在所有输入 I。

作者注意到 bin 容量为 1 的 Bin-Covering 问题与具有两倍 bin 容量 (2) 的最大资源 Bin-Packing 之间的相似性。在 Bin-Covering 中，目标是分配项目以达到或超过尽可能多的 bin 的容量。

其它你可能感兴趣的问题
上一篇是否存在某种形式的 GMSH 文档？ 下一篇Hartree Fock 迭代问题