4

我正在研究一种装箱问题，但并不完全相同。该问题要求将n件物品放入最少数量的箱子中，但总重量不会超过箱子的容量。（经典定义）

不同之处在于：每个项目都有一个权重和bound ，并且 bin 的容量由该 bin 中项目的最小边界动态确定。

例如，我有四个项目 A[11,12], B[1,10], C[3,4], D[20,22] ( [weight,bound] )。现在，如果我将物品 A 放入一个 bin 中，称它为 b1，那么 b1 的容量变为 12。现在我尝试将物品 B 放入 b1，但失败了，因为总重量为 11+1 =12，容量为b1 变为 10，小于总权重。因此，B 被放入 bin b2，其容量变为 10。现在，将项目 C 放入 b2，因为总重量为 1+3 =4，而 b2 的容量变为 4。

我不知道这个问题是否已经在某些地区以某种名称解决了。或者它是在某处讨论过的装箱变体。我不知道这是否是发布问题的正确位置，感谢任何帮助！

4

4 回答 4

3

通常对于 NP-hard 问题的算法设计，有必要重用技术而不是整个算法。在这里，使用带有列生成的分支定界的标准装箱算法可以很好地进行。

这个想法是我们制定了一个巨大的集合覆盖实例，其中集合是适合单个箱的项目集合。整数规划对于普通集合覆盖来说是一种很好的技术，但是集合太多，我们需要做其他事情，即列生成。集合和列之间是一一对应的，所以我们撕掉了线性规划求解器中使用蛮力找到一个好的列进入并用求解器替换它原来是背包的部分这个问题的类比。

这个修改后的背包问题是，给定具有重量、利润和界限的物品，找到总重量小于最小界限的最有利可图的物品集。求解具有小整数权重的背包的动态程序在不损失效率的情况下愉快地转移。只需按降序对项目进行排序；然后，当形成涉及最近项目的集合时，重量限制就是该项目的界限。

于 2015-06-14T13:43:59.300 回答
1

以下内容基于Anony-mouse 的回答。我不是算法专家，所以将以下内容视为“只是我的两分钱”，因为它们的价值。

我认为 Anony-mouse 从最小的项目（绑定）开始是正确的。这是因为您添加的物品越多，垃圾箱的容量就会越小。一个箱子的最大容量是由放入其中的第一个物品决定的，在那之后它永远不会变大。

因此，与其从一个大垃圾箱开始慢慢减少其容量，并且不必担心取出以前适合的过大物品，让我们尽量保持垃圾箱的容量尽可能恒定。如果我们可以保持垃圾箱的容量稳定，我们可以使用对“绑定”一无所知的“标准”算法。

所以我建议这样做：

  1. 按绑定对所有项目进行分组。

    这将允许您对每个组使用标准的装箱算法，因为如果所有项目都具有相同的界限（即界限是恒定的），则基本上可以忽略它。现在，绑定意味着您提前知道生成的垃圾箱的容量。

  2. 从具有最小界限的组开始，对其项目执行标准箱包装。

    这将导致 1 个或多个 bin 的容量等于其中所有项目的界限。

  3. 继续具有下一个较大界限的项目组。查看是否有任何物品仍可放入已存在的垃圾箱（即前面步骤产生的垃圾箱）。

    注意 bound 可以再次被忽略；由于所有预先存在的垃圾箱的容量已经小于这些附加物品的限制，因此垃圾箱的容量不会受到影响；只有重量是相关的，所以你可以使用“标准”算法。

    我怀疑这一步是（多个）背包问题的一个实例，因此请查看背包算法来确定如何将这些物品分配到预先存在的、部分装满的箱子中。

  4. 上一个组中的项目组可能仅被部分处理，可能还有剩余的项目。这些将进入一个或多个新垃圾箱：基本上，重复步骤 3。

  5. 重复上述步骤（从 3 开始），直到没有剩余物品。

于 2015-06-14T08:51:48.983 回答
1

它仍然可以写成 ILP 实例，如下所示：

制作一个x_{i,j}表示 item 是否j进入 bin的二进制i变量y_i，表示是否i使用 bin 的辅助变量c_i，确定 bin 容量的辅助变量i，并且有常量s_j（ item 的大小j）b_j（ item 的边界j）和M（足够大的常量） ， 现在

minimize sum[j] y_j

subject to:
1:   for all j:
         (sum[i] x_{i,j}) = 1
2:   for all i,j:
         y_i ≥ x_{i,j}
3:   for all i:
         (sum[j] s_j * x_{i,j}) ≤ c_i
4:   for all i,j:
         c_i ≤ b_j + (M - M * x_{i,j})
5:   x_{i,j} ϵ {0,1}
6:   y_i ϵ {0,1}

约束意味着

  1. 任何物品都在一个箱子里
  2. 如果一个项目在一个 bin 中，则使用该 bin
  3. 垃圾箱中的物品不超过该垃圾箱的容量
  4. 箱子的容量不超过其中物品的最低限度（如果您选择的 M 不小于最高界限，则具有大 M 的东西可以防止不在箱子中的物品改变容量）
  5. 6.，变量是二进制的。

但完整性差距可能是巨大的。

于 2015-06-14T09:16:26.877 回答
0

首先，我可能完全错了，可能存在比我更好的算法。

Bin 打包是NP 难的，可以使用First Fit等经典算法有效解决。对此也有一些改进。Korf 算法

我的目标是通过按界限对物品进行分类来将其减少到正常的垃圾箱包装。步骤是

  1. 按界限对项目进行排序：按界​​限对项目进行排序将有助于我们安排箱子，因为限制条件是界限的最小值。

  2. 将最小的项目（按绑定）插入垃圾箱

  3. 检查下一个项目（按边界排序）是否可以共存于此 bin 中。如果它可以将项目也保留在 bin 中。如果不能，则尝试将其放入另一个 bin 或为其创建另一个 bin。
  4. 重复此过程，直到所有元素都排列好。该过程以边界的升序重复。

我认为这几乎可以解决问题。如果没有，请通知我。我正在尝试实施相同的方法。如果有任何建议或改进也请告诉我。：） 谢谢

于 2015-06-14T08:06:40.107 回答