algorithm - 算法设计手册中的乐透彩票覆盖范围？

Question

我正在阅读 Steven S. Skiena 的算法设计手册。我正在阅读有关彩票问题的第一章。 Skiena 声称他的第一个保证获胜的最佳彩票数量的解决方案是不正确的。我不明白他的下一个也是最后一个解决方案是如何正确的？

在figure 1.11他说:保证从 {1,2,3,4,5} 仅使用门票 {1,2,3} 和 {1} 中的一对获胜， 4, 5} 还有一个图表。我很困惑为什么其他数字不在那里？例如，如果中奖号码是 (3,4)、(2,4)、(2,5)、(3,5) 等等...？明明不能把票拼在一起，这怎么解释呢？在彩票中，如果中奖号码是 3 和 5，则您必须有一张按某种顺序排列有 3 和 5 的彩票。有人可以解释一下吗？

Answer 1

在例子中

• n = 5 - 来自通灵者的数字
• j = 3 - n中的中奖号码个数
• k = 3 - 票上的槽数
• l = 2 - 获得奖品所需的匹配次数

让这个案例变得简单的原因是票上的所有数字都必须在 1..5 之间。这是因为 j=k，表示落在 1 到 5 之间的中奖号码的数量与彩票上的插槽数量相匹配。

所以拿票 {1, 2, 3} 和 {1, 4, 5}。这确实意味着您错过了匹配项 {3, 5}，但如果票上有数字 {3, 5}，则票上的另一个号码必须来自集合 {1, 2, 4}。如果是 1 则匹配 3 已被第一张票选中，如果是 2 则相同，如果是 5 则第二张票捕获了它。