1

给定一组项目（大小从 1 到 100 的任意位置）和一些箱（1 到 15）。每个项目都有一个箱子集，该项目可以分配到，以及哪个箱最好、次佳、等等，只是为了它。项目也有自然顺序，下面用命名来表示，例如，项目 1 在项目 2 之前。每个箱子的容量在 1 到 5 之间（每个物品的重量相同，即 1。）

示例输入可以是三个箱子和六个物品（- 表示箱子不在物品的可用集合中，即不能与它一起打包）：

      | bin1 bin2 bin3 | 仓1仓2仓3   
------------------------------------ -------------- --
项目1 | 1 2 - 容量 | 4 4 5
项目2 | - 1 2               
项目3 | 2 1 3
项目4 | 1 2 3
项目5 | 1 - 2
项目6 | 1 2 3

目标是（为了在发生冲突时每个目标完全覆盖任何较低的目标，例如，无论使用多少箱或忽略偏好，打包五个物品总是优于四个）：

  1. 最大化包装的物品数量
  2. 按自然顺序包装物品，例如，如果总箱容量为 1 并且有两个物品，则将包装 item1 而 item2 不包装
  3. 最小化使用的垃圾箱数量
  4. 根据每个项目的 bin 偏好和自然顺序打包每个项目，即第一个偏好中的 item1 和第二个中的 item2 优于第二个中的 item1 和第一个中的 item2
  5. 在两个解决方案无法通过这些目标区分的情况下，任何一个解决方案都可以接受更高的排名，例如，作为实施的副作用或只是任意的平局。

所以上面的输入将被打包为：

      | 仓1仓2仓3
----------------------
项目1 | X            
项目2 | X     
项目3 | X     
项目4 | X          
项目5 | X      
项目6 | X

然后的问题是阅读/审查什么来帮助我想出解决这个问题的算法想法，第一段的输入大小和几秒钟的时间限制，即不是蛮力（或至少任何蛮力到目前为止我已经想到的力量。）我正在使用 Ruby 和 C，但是在这个林木蹒跚的阶段，语言并没有过度相关。

我将不胜感激任何阅读建议、关于算法组合的想法，或者只是关于澄清问题陈述的想法......

更新 1

不太清楚，虽然有许多算法涵盖了这方面的各个部分，但我的困难在于找到（或可能识别）一起处理所有标准的信息，特别是在容量过剩和项目冲突时尽量减少使用的垃圾箱数量-bin 设置和项目偏好，希望在以下示例中更清楚地显示：

      | bin1 bin2 bin3 | 仓1仓2仓3   
------------------------------------ -------------- --
项目1 | 1 2 3 容量 | 3 2 3
项目2 | 1 2 3          
项目3 | - 1 2

虽然 bin1 是最首选的，但 item3 根本不能放在其中，而 bin2 是所有项目的第二首选，它只能容纳三个项目中的两个。所以正确的赋值集 (x) 实际上是最不喜欢的 bin：

      | 仓1仓2仓3
----------------------
项目1 | X  
项目2 | X  
项目3 | X

更新 2 我用有关目标如何关联的信息重新编写了描述，并删除了 bin 优先级变量，因为它只会降低找到答案的可能性，并且可以在我正在处理的系统的其他地方解决。

4

3 回答 3

1

这让我想起了用于将医学院毕业生安排在住院医师项目中的“匹配”算法。如果您将项目视为学生，将他们的垃圾箱偏好视为排名列表，将垃圾箱视为医院怎么办？

基本上，您浏览项目列表，并为每个项目找到它最喜欢的垃圾箱。检查垃圾箱： 您是否有空间放置此物品，如果没有，您是否比您目前拥有的任何物品更喜欢它？ 如果否，请从项目列表中划掉此垃圾箱，然后移至该项目的下一个选择。
如果是，则将该项目放入垃圾箱，并将被替换的项目（如果有）放回不匹配的池中。

您的问题和居住匹配之间的区别在于您不会预先修复垃圾箱的偏好。相反，您将使用一个规则，该规则更喜欢使垃圾箱最接近 100% 满的物品。

我唯一担心的是这种修改可能会使算法不稳定。但它是如此简单的算法，它可能值得一试。

于 2011-02-21T17:24:45.123 回答
1

这是一个二分匹配问题，可以在多项式时间内解决。

http://en.wikipedia.org/wiki/Matching_(graph_theory)#Maximum_matchings_in_bipartite_graphs

于 2011-02-21T17:46:37.703 回答
1

假设有 n 个项目和 b 个 bin，每个 bin 的大小为 s。您添加的约束的顺序实际上大大简化了问题。

它们具体意味着我们应该始终选择项目 1、2、...、m 以获得最大的 m <= n 以适应分配的 bin 数量（因为根据规则 1，选择较小的数字必然会产生更差的解决方案） . 物品将按此顺序装入箱中，可能有一些箱未装满（因为在箱内或跨箱重新排列物品会根据规则 2 产生更差的解决方案）。有2种情况：

  1. m < n，这意味着我们无法容纳所有项目。在这种情况下，所有 b 个 bin 将按顺序与第 1 m 个项目紧密包装，我们就完成了。
  2. m = n，在这种情况下，我们可以拟合所有项目。我们现在考虑这种情况的子情况。

在这种情况下，有可能紧紧地包装箱将留下最终块 0 < e <= b 的箱完全空。在这种情况下，丢弃最后的 e 个空箱并继续（因为使用更多箱会根据规则 3 产生更差的解决方案）。在任何情况下，调用最后剩余的 bin 数量 r。（r = b - e。）

我们现在确切地知道我们将使用哪些物品和哪些垃圾箱。我们也知道物品必须包装的顺序。由于排序约束，我们可以将关于哪些箱不完全填充的决定视为如何将“start-next-bin”指令注入到项目的有序列表 1、2、...n 中的问题。我们最多可以注入这些指令中的 r-1 个。

这个问题可以使用动态规划在 O(nrs) 时间内解决。本质上我们计算函数：

f(i, j, k) = 前 i 个项目占据前 j 个盒子的最佳解决方案的得分，其中 k 个项目恰好在第 j 个盒子中。

复发是：

f(i, j, 0)     = max(f(i, j-1, k)) over all 0 <= k <= s
f(i, j, k > 0) = f(i-1, j, k-1) + q(i, j)

其中 q(i, j) 是将项目 i 分配给框 j 的质量得分。（正如我在您帖子的评论中提到的那样，您需要决定以某种方式为将任何项目 i 放置到任何框 j 中的位置分配分数，大概基于 i 的偏好得到满足的程度。如果使用起来更容易“ badness" 值而不是质量值，只需将 a 更改max()为 amin()并将-infinity下面的边界值更改为infinity.)

第一个方程表示最右边的 bin 为空的前 i 个项目的解决方案的最佳分数等于通过考虑没有该 bin 的前 i 个项目的每个解决方案可以找到的最佳分数。这些候选解决方案包括可以打包前一个 bin 的所有方式，包括将其留空。

第二个等式表明，最右边的 bin 不为空的前 i 个项目的最佳分数只需将放置最后一个项目的质量分数与将前 i-1 个项目放置在相同数量的 bin 中的最佳分数相加即可.

边界条件为：

f(0, 0, 0) = 0
f(i, 0, k) = -infinity for all other i and k

在计算每个 0 <= i <= n、0 <= j <= r 和 0 <= k <= s 的 f(i, j, k) 的值并将它们存储在一个表中之后，f(n, r , s) 将给出最终解决方案的最佳分数。尽管这仅给出最大值的分数，但可以通过从末尾追溯 f(i, j, k) 矩阵来找到实际的最优解，在每 k = 0 步寻找前导状态 (即max()) 下的替代方案必须导致当前状态。（在给出相同分数的情况下，可能会出现多个备选方案max()，在这种情况下存在多个最优解决方案，并且可以遵循这些路径中的任何一个来找到其中一个。）

于 2011-02-23T11:48:40.977 回答