给定一组项目（大小在1到100之间）和多个箱子（1到15） . 每个项目具有可以分配项目的箱子集，并且优先排序哪个箱子最好，第二好，等等，只是为了它 . 项目也有一个自然顺序，下面用命名表示，例如item2之前的item1 . 每个箱子的容量在1到5之间（每个物品具有相同的重量，即1） .
一个示例输入可以是三个箱子和六个物品（ - 表示箱子不在物品的可用集合中，即不能用它打包）：
| bin1 bin2 bin3 | bin1 bin2 bin3
------------------------ ----------------------------
item1 | 1 2 - capacity | 4 4 5
item2 | - 1 2
item3 | 2 1 3
item4 | 1 2 3
item5 | 1 - 2
item6 | 1 2 3
目标是（按照每个目标在发生冲突时完全覆盖任何较低目标的顺序，例如，无论使用多少个箱子或忽略偏好，包装五个项目总是好于四个）：
-
最大化包装的物品数量
-
以自然顺序打包物品，例如，如果总箱容量为1且有两个物品，则物品1将被打包而物品2不会
-
最小化使用的箱数
-
根据其首选项和自然顺序打包每个项目，即第一个首选项中的item1和第二个中的item2优于第二个中的item1和第一个中的item2
在这两个解决方案无法通过这些目标区分的情况下，任何一种解决方案都可以接受更高的排名，例如，作为实施的副作用或只是任意打破平局 .
所以上面的输入将打包为：
| bin1 bin2 bin3
------------------------
item1 | x
item2 | x
item3 | x
item4 | x
item5 | x
item6 | x
那么问题是什么阅读/审查，以帮助我提出解决这个问题的算法思路，从第一段的输入大小和几秒的时间约束，即，不是暴力（或至少任何粗暴）到目前为止，我已经构思过了 . ）我正在使用Ruby和C语言，但语言在这个树林里磕磕绊绊并不过分 .
我会感激任何阅读建议，关于算法组合的想法，或只是澄清问题陈述的想法......
Update 1
更不清楚，虽然有许多算法涵盖了这一部分的各个部分，但我的困难在于找到（或者可能识别）处理所有标准的信息，特别是当存在容量过剩和冲突项目时使用的箱数最小化-bin集和项首选项，希望在以下示例中更清楚地显示：
| bin1 bin2 bin3 | bin1 bin2 bin3
------------------------ ----------------------------
item1 | 1 2 3 capacity | 3 2 3
item2 | 1 2 3
item3 | - 1 2
虽然bin1是最受欢迎的，但是item3根本不能放在其中，而bin2是所有项目的下一个最优选项目，它只能容纳三个项目中的两个 . 所以正确的赋值集（x）实际上是最不喜欢的bin：
| bin1 bin2 bin3
------------------------
item1 | x
item2 | x
item3 | x
Update 2 我使用有关目标如何关联的信息重新描述了描述并删除了bin优先级的变量，因为它只会使找到答案的可能性降低，并且可以在我正在研究的系统中的其他地方解决 .
3 回答
假设有n个项目和b个bin，每个bin的大小为s . 您添加的约束的排序实际上简化了问题 .
它们特别指的是我们应该总是选择项目1,2，...，m来获得最大的m <= n，它将适合分配的数量的箱子（因为选择较小的数字必然会产生规则1的更糟糕的解决方案） . 物品将按此顺序装在垃圾箱中，可能还有一些垃圾桶未完全填满（因为在垃圾箱内或垃圾箱内重新排列物品会因规则2而产生更糟糕的解决方案） . 有2种情况：
m <n，意味着我们无法容纳所有项目 . 在这种情况下，所有b箱将按顺序紧紧包装第1 m个项目，我们就完成了 .
m = n，在这种情况下我们可以适合所有项目 . 我们现在考虑这个案例的子句 .
在这种情况下，紧密的填料箱可能会使箱的0 <e <= b的最终块完全排空 . 在这种情况下，丢弃那些最后的空箱并继续进行（因为使用更多的箱会因规则3而产生更糟的解决方案） . 在任何情况下，调用最后剩余的垃圾箱数量r . （r = b - e . ）
我们现在确切地知道我们将使用哪些物品和哪些箱子 . 我们也知道必须包装物品的顺序 . 由于排序约束，我们可以将关于哪些箱子未完全填充的决定视为 how to inject "start-next-bin" instructions into the ordered list 1, 2, ... n of items 的问题 . 我们可以注入这些指令的r-1 .
使用动态编程可以在O（nrs）时间内解决此问题 . 基本上我们计算函数：
f(i, j, k) = the score of the best solution in which the first i items occupy the first j boxes, with exactly k items in the jth box.
重现是：
其中q（i，j）是将项目i分配给方框j的质量分数 . （正如我在你的帖子评论中所提到的，你需要决定某种方式将任何项目i的位置分配到任何方框j中，大概是基于我的"badness"值比质量值更容易使用"badness"值，只需将
max()更改为min()，将-infinity边界值更改为infinity. ）第一个等式表示a的最佳分数最右边的bin为空的前i个项目的解决方案等于通过考虑没有该bin的第一个i项目的每个解决方案可以找到的最佳分数 . 这些候选解决方案包括前一个bin可以打包的所有方式，包括将其留空 .
第二个等式表示，最右边的箱子不为空的第一个i项目的最高分数只需添加质量得分，将最后一个项目放入最佳分数，以便将第一个i-1项目放在相同数量的箱子中 .
边界条件是：
在计算每个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()下的几个替代方案给出相同的分数，在这种情况下存在多个最优解，并且可以遵循这些路径中的任何一个来找到它们中的一个 . ）这让我想起了"Match" algorithm曾经将医学院毕业生安置在住院医师计划中 . 如果您对待学生这样的项目，他们的箱子偏好（如排名列表）以及像医院这样的箱子会怎么样？
基本上，您浏览项目列表，并为每个项目找到它最喜欢的bin . 用垃圾箱检查：你有这个项目的空间，如果没有，你比你现有的任何项目更喜欢它吗？如果不是，请从下一个项目's list, and move to the item'下划线 .
如果是，请将此项目放在bin中，并将移位的项目（如果有）放回到不匹配的池中 .
您的问题与居住匹配之间的区别在于您不会预先修复垃圾箱的偏好 . 相反，您会使用一个规则，该规则更喜欢使bin最接近100％的项目 .
我唯一担心的是这种修改可能会使算法不稳定 . 但它是一个如此简单的算法，它可能值得尝试 .
这是一个二分匹配问题，可以在多项式时间内求解 .
http://en.wikipedia.org/wiki/Matching_(graph_theory)#Maximum_matchings_in_bipartite_graphs