我正在阅读Steven S. Skiena的算法设计手册.我在第一章阅读有关彩票问题的内容.他声称他的第一个解决方案是保证获胜的最佳票数是不正确的.我不明白他的下一个和最后的解决方案是如何正确的？
在图1.11中,他说:仅使用门票{1,2,3}和{1,4,5}来保证{1,2,3,4,5}中的获胜对,并且有一个图表.我很困惑为什么其他数字不在那里？例如,如果中奖号码是(3,4),(2,4),(2,5),(3,5)等,该怎么办？你显然无法将门票合并在一起,所以我们如何解释这个？有人可以解释一下吗？在彩票中,如果他们说中奖号码分别是3和5,那么你必须拥有一张票数为3和5的票.我对此感到失落.
Col*_*ack 12
在示例中
这个案例的简单之处在于票证上的所有数字必须介于1..5之间.这是因为j = k,意味着落在1和5之间的中奖号码的数量与票证上的插槽数量相匹配.
所以拿票{1,2,3}和{1,4,5}.这确实意味着你错过了比赛{3,5}但是如果数字{3,5}在票上,那么票上的另一个数字必须来自集合{1,2,4}.如果是1那么比赛3已经由第一张票进行了检查,如果它是2那么然后相同,如果它是5然后第二张票抓住它.