我有以下情况（对于长度的初步道歉，但我想尽可能描述）：
我收到了一份“食谱”（Ri）列表，必须按照给出的顺序完成，才能完成给定的任务。每个配方都包含完成它所需的部分 (Pj) 列表。一个配方通常需要多达 3 或 4 个部分，但可能需要多达 16 个。示例配方列表可能如下所示：
- R1 = {P1}
- R2 = {P4}
- R3 = {P2，P3，P4}
- R4 = {P1，P4}
- R5 = {P1, P2, P2} //请注意，可能需要超过 1 个给定部分。（这里，P2）
- R6 = {P2，P3}
- R7 = {P3，P3}
- R8 = {P1} //请注意，配方可能会在列表中重复出现。（与 R1 相同）
最长的列表可能包含几百个食谱，但通常包含一些食谱的多次重复，因此消除相同的食谱通常会将列表减少到少于 50 个独特的食谱。
我有一组机器 (Mk)，每台机器都经过预编程（这种情况发生一次，在列表处理开始之前）以生产部分（或全部）可用类型的零件。
履行过程的迭代发生如下：
- 列表中的下一个配方将呈现给机器库。
- 在每台机器上，选择其中一个可用程序来生产此配方所需的零件之一，或者，如果此配方不需要它，则将其设置为“离线”。
- 转动“曲柄”，每台机器（尚未“离线”）吐出一个零件。
- 将曲柄转动一圈产生的零件组合起来就可以完成配方。顺序无关紧要，例如，履行配方{P1，P2，P3}与履行配方{P1，P3，P2}相同。
这些机器即时、并行运行，并且拥有无限的原材料，因此没有资源或时间/调度限制。机器组的大小 k 必须至少等于最长配方中元素的数量，因此与上述配方长度具有大致相同的范围（通常为 3-4，可能最多 16 个）。因此，在上面的示例中，k=3（由 R3 和 R5 的大小决定）似乎是一个合理的选择。
手头的问题是如何对机器进行预编程，以便银行能够完成给定列表中的所有食谱。机器库共享一个公共内存池，因此我正在寻找一种算法，该算法可以生成一种编程配置，以消除（完全或尽可能多地）机器之间的冗余，从而最大限度地减少总内存负载量。机器库大小 k 是灵活的，即，如果将机器数量增加到超过给定列表中最长配方的长度会为列表产生更优化的解决方案（但保持 16 的硬限制），那很好。
目前，我认为这是一个单成本问题，即每个程序需要相同数量的内存，尽管我希望将来可以灵活地添加每个程序的权重。在上面的示例中，考虑到所有配方，P1 最多出现一次，P2 最多出现两次（在 R5 中），P3 最多出现两次（在 R7 中），P4 最多出现一次，所以我理想地希望实现与此匹配的配置 - 只有一台机器配置为生产 P1，两台机器配置为生产 P2，两台机器配置为生产 P3，一台机器配置为生产 P4。对于上述示例，使用机器组大小 k=3 的一种可能的最小配置是：
- M1 被编程为产生 P1 或 P3
- M2 被编程为产生 P2 或 P3
- M3 被编程为产生 P2 或 P4
由于这里没有作业车间类型的约束，我的直觉告诉我这应该简化为一个集合覆盖问题——就像在设计数字系统中发现的最小单一集合覆盖问题一样。但我似乎无法将我对这些算法的（诚然有限的）知识适应这种情况。有人可以确认或否认这种方法的可行性，并且无论哪种情况，都可以向我指出一些有用的算法吗？我正在寻找可以集成到现有代码块中的东西，而不是像 Berkeley's Espresso 这样预先打包的东西。
谢谢！