给定一组项目(大小从 1 到 100 不等)和多个 bin(1 到 15)。每个项目都有一个 bin 子集，可以将项目分配到该子集以及哪个 bin 最好的偏好排序，次优等，只为之。项目也有一个自然顺序，下面用命名表示，例如，item1 在 item2 之前。每个箱子的容量在 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
目标是(为了让每个目标在发生冲突时完全覆盖任何较低的目标，例如，无论使用多少箱子或忽略偏好，包装 5 件元素总是比 4 件好):
- 最大化包装元素的数量
- 按自然顺序包装元素，例如，如果总箱容量为 1 且有两件元素，则元素 1 将被打包而元素 2 不会
- 尽量减少使用的垃圾箱数量
- 根据其 bin 偏好和自然顺序打包每个项目，即 item1 在其第一偏好和 item2 在其第二优于 item1 在其第二和 item2 在其第一
- 在这些目标无法区分两个解决方案的情况下，任一解决方案都可以排名更高，例如，作为实现的副作用或只是任意打破平局。
所以上面的输入将被打包为:
| bin1 bin2 bin3 ------------------------ item1 | x item2 | x item3 | x item4 | x item5 | x item6 | x
接下来的问题是阅读/复习什么可以帮助我想出解决这个问题的算法思路，使用第一段的输入大小和几秒钟的时间限制，即，不是蛮力(或在至少我到目前为止想到的任何蛮力。)我正在使用 Ruby 和 C，但在这个阶段，语言并不过分相关。
我将不胜感激任何阅读建议、关于算法组合的想法，或者只是关于澄清问题陈述的想法......
更新 1
不太清楚，虽然有许多算法涵盖了这方面的各个部分，但我的困难在于找到(或者可能识别)处理所有标准的信息，特别是在容量过剩和冲突时尽量减少使用的箱子数量item-to-bin sets 和 item preferences，希望在以下示例中更清楚地显示:
| 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
更新 2 我用有关目标如何关联的信息重新编写了描述，并删除了 bin 优先级变量，因为它只会降低找到答案的可能性，并且可以在我正在处理的系统中的其他地方解决。
最佳答案
假设有 n 个元素和 b 个箱子，每个箱子的大小为 s。您添加的约束的顺序实际上大大简化了问题。
它们的具体意思是，我们应该始终选择项目 1、2、...、m 来满足最大的 m <= n，这将适合分配的 bin 数量(因为选择较小的数量必然会产生更差的解决方案规则1)。元素将按此顺序包装在箱子中，可能还有一些箱子没有完全装满(因为根据规则 2，在箱子内或跨箱子重新排列元素会产生更糟糕的解决方案)。有2种情况:
- m < n，意味着我们不能装下所有的项目。在这种情况下，所有 b 个箱子都将按顺序与第 m 个项目紧密包装，我们就完成了。
- m = n，在这种情况下我们可以适应所有项目。我们现在考虑这种情况的子情况。
在这种情况下，紧密打包箱子可能会留下最后一 block 0 < e <= b 的箱子完全空着。在这种情况下，丢弃最后的 e 个空箱子并继续(因为根据规则 3，使用更多的箱子会产生更糟糕的解决方案)。在任何情况下，将最终剩余的 bin 数量称为 r。 (r = b - e.)
我们现在确切地知道我们将使用哪些元素和哪些垃圾箱。我们也知道元素的包装顺序。由于顺序约束，我们可以将关于哪些 bin 未完全填充的决定视为如何将“start-next-bin”指令注入(inject)有序列表 1, 2, ... n 的问题项目。我们最多可以注入(inject) r-1 条这些指令。
这个问题可以使用动态规划在 O(nrs) 时间内解决。本质上我们计算函数:
f(i, j, k) = 前 i 个项目占据前 j 个框的最佳解决方案的分数，第 j 个框正好有 k 个项目。
递归是:
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 的位置分配分数，大概是基于我的偏好得到满足的程度。如果它更容易使用“badness"值比质量值，只需将 max() 更改为 min() 并将下面的 -infinity 边界值更改为 无穷大.)
第一个方程表示，最右边的 bin 为空的前 i 项的解决方案的最佳分数等于通过考虑没有该 bin 的前 i 项的每个解决方案可以找到的最佳分数。这些候选解决方案包括可以打包前一个箱子的所有方式，包括也将其留空。
第二个等式表示最右边的 bin 不为空的前 i 个项目的最佳分数只需将放置最后一个项目的质量分数与放置第 i-1 个项目的最佳分数相加即可箱数。
边界条件是:
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() 下的多个备选方案给出相同分数的情况，在这种情况下存在多个最佳解决方案，并且可以遵循这些路径中的任何一个来找到其中一个。)
关于algorithm - 寻找有关理解特定组合优化问题的建议，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5068245/