5

我正在从以下位置阅读文章。这是文本片段表单文档。

关联

找到保证获胜的最小门票集的问题并非易事。鉴于 R 中的 P 个结果将来自算命者集合，不难看出有 NCP = (N/P!)/(NP)！中奖彩票中可能出现的算命者集合中的可能 P 子集。如果我们从算命者集合 W 次中选择所有 P 子集并任意填充剩余的 RP 槽，则获得的票集将至少有 W 次出现每个 P 子集，并保证我们 W 赢。但是，这样的集合不必是最小的集合，在大多数情况下也不是。

我们从算命先生的承诺中得知，其中一个 P 子集将出现在中奖彩票中。两个 P 子集的差异可能小于 J 个数。当这种情况出现时，就共享的 J 个数而言，子集被称为相互重叠或覆盖，并且只有一个 P 子集必须在购买的票中。这个现象最好用一个例子来说明。假设我们正在玩 PICK-4 Lotto 并且需要 2/4 的胜利。因此 R=4，J=2 和 W=1。此外，让我们假设算命先生从一组 5 个数字中预测 3 个数字（即 P=3 和 N=5 ）。如果所有 P 子集都取自算命先生集合并任意填充以完成彩票，我们将有一组十张彩票，保证 2/4 获胜（见图 1）。然而，由于有几个两个数字重叠，因此也可以从该集合中排除一些票。例如，子集 {3, 4, 5} 与 {1, 3, 5} 仅相差一个数字，在购买的门票中同时使用这两个是浪费的。我们可能认为不包括 {3, 4, 5} 将允许失败的可能性，但事实并非如此，因为如果 {3, 4, 5} 发生我们将在 {1, 3, 5}我们买来领奖！类似地，可以有更多的冗余 P 子集。图 2 显示了一个最佳解决方案。我们的彩票问题是从算命者集合中找到最小的 P 子集集合，该集合通过将重叠次数保持在最低限度来保证指定的获胜次数。

我的问题是

  1. 正如作者所提到的“如果所有的 P 子集都是从算命先生集合中取出并任意填充以完成票证，我们将有一组十张票”因为缺少文章表中的任何人都可以在这里帮助我什么是 10门票？

  2. 在上面的示例中，如果出现 1 和 3，并且如果我们没有选择 {1, 3, 5}，我们如何才能在这里获胜？

  3. 谁能想出文章中缺少的图2？

感谢！

4

2 回答 2

0

  1. 这是10张票的低效清单

    {1, 2, 3, 6}
{1, 2, 4, 6}
{1, 2, 5, 6}
{1, 3, 4, 6}
{1, 3, 5, 6}
{1, 4, 5, 6}
{2, 3, 4, 6}
{2, 3, 5, 6}
{2, 4, 5, 6}
{3, 4, 5, 6}

  2. 亩。为了获胜，我们需要匹配 4 个中的 2 个。所以不是出现 1 和 3 的情况，而是出现一组特定的 3 个，我们只需要匹配其中的 2 个。

  3. 我认为这是最优的。

    {1, 2, 3, 4}

但我并不完全肯定我可以选择 4 个。如果我只允许每张票选择 3 个，那么最佳组合将是：

    {1, 2, 3}
    {2, 3, 4}
于 2012-10-31T15:55:02.483 回答
0

两张票分别是：

{ 1, 3, 5, X }

{ 2, 4, 5, X }

其中 X 是不影响解的任意选择的数字。

于 2012-10-31T16:50:12.923 回答