13

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

在图 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 的彩票。有人可以解释一下吗？

4

2 回答 2

18

在示例中

  • 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 则第二张票接住它。

于 2013-10-20T19:25:00.760 回答
2

在图 1.11 中，每张彩票上的插槽数是 3。所以有 3 个中奖号码。使用 {1,2,3} 和 {1,4,5} 两张彩票，保证您在 3 个中奖号码中至少有 2 个。

于 2013-08-12T04:46:16.843 回答