寻找不同数量参考项的最优组合以最大化完全满足的订单数

结论：不能用贪心算法实现该需求 #

贪心算法的核心是每次做局部最优选择（比如选当前能新增满足最多订单的参考项），但这种策略无法保证全局最优，下面用具体反例说明：

反例演示

假设有如下订单集合：

order_book = [
    {"id": 1, "reference_items": ["x"]},
    {"id": 2, "reference_items": ["y"]},
    {"id": 3, "reference_items": ["z"]},
    {"id": 4, "reference_items": ["a", "b"]},
    {"id": 5, "reference_items": ["a", "b"]},
    {"id": 6, "reference_items": ["a", "b"]}
]

当寻找2个参考项的最优组合时：

• 贪心逻辑会优先选择单个参考项中覆盖订单最多的（x/y/z，各自仅能覆盖1个订单），第二步再选另一个同类项，最终组合如(x, y)仅能满足2个订单。
• 但真正的最优组合是(a, b)，可以满足3个订单（订单4、5、6），显然贪心得到的是次优结果。

问题本质 #

这个需求属于带大小约束的集合覆盖变种：要求选出大小为k的参考项子集，使得被完全包含的订单数最大化。这类问题是NP-hard的，贪心算法只能提供近似解，无法保证全局最优。若要精确求解，小规模数据可采用枚举或动态规划，大规模数据则需要依赖启发式算法。

内容的提问来源于stack exchange，提问作者Developppeur