给定一组项目(大小从 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 并且有两个物品,则将包装 item1 而 item2 不包装
- 最小化使用的垃圾箱数量
- 根据每个项目的 bin 偏好和自然顺序打包每个项目,即第一个偏好中的 item1 和第二个中的 item2 优于第二个中的 item1 和第一个中的 item2
- 在两个解决方案无法通过这些目标区分的情况下,任何一个解决方案都可以接受更高的排名,例如,作为实施的副作用或只是任意的平局。
所以上面的输入将被打包为:
| 仓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 优先级变量,因为它只会降低找到答案的可能性,并且可以在我正在处理的系统的其他地方解决。