由于潜在的假阳性,这种情况会将精确的覆盖物减少到子集中的情况下吗?
-
29-09-2020 - |
题
删除多组和设置,其中包含不存在的元素 $ s $ 。
$ s $ = $ [9,6,7,4,5,1,8] $
$ c $ = $ [[9,6,7],[4,5],[1, 8] $
将 $ c $ c $ 中的值与 $ s $ 中共享索引值的值。 (这必须在触摸 $ s $ )之前完成。
$ c $ = $ [[1,2,3],[4,5],[6, 7] $
并为 $ s $
$ s $ = $ [1,2,3,4,5,6,7] $
square每个 $ x $ 整数在 $ s $ 和 $ C $
$ f(x)$ = $ x ^ 2 $ , $ x∈s $ 然后 $ c $
$ s $ = $ [1,4,9,16,25,36,49] $
$ c $ = $ [[1,4,9],[16,25],[36, 49] $
然后删除具有重复总和的所有集合以防止误报。这意味着没有 $ [1],[1] s ... $ ,可以使用,总结到 $ s $ ,这也意味着 $ [1,4,9] $ 或 $ [ 4,9,1] $ 。 (虽然留下一个!)- 在转换完成后,使用子集 - 和求解器并将总和定义为 $ 140 $ ( $ s $ )
- 将整数列表定义为 $ c $ = $ [[14],[41] ,[85]] $
- 运行算法并获得解决方案
问题
将精确覆盖的这种情况降低到子集中,每次都会产生假阳性?
解决方案
如果你真的不确定减少是否有效,它可能不会。每当你减少减少时,你应该始终有一个如何证明它正确的计划。
在这种情况下,我们希望看到 $ 1 ^ 2 + 2 ^ 2 + 3 ^ 2 + ... + n ^ 2 $ 可以以其他方式写成一总体(这将是假阳性)。
我们有 $ 4 ^ 2= 2 ^ 2 + 2 ^ 2 + 2 ^ 2 + 2 ^ 2 $ 。这足以构建一个反例。
let $ s={1,2,3,4,5,6,7 \} $ 和 $ c={\ {1,2 \},\ {2,5 \},\ {2,6 \},\ {2,7 \},\ {1, 3,4,5,6,7 \} \} $ 。
没有确切的封面(获取 $ 4 $ 的唯一方法是使用 $ \ {1,3, 4,5,6,7 \} $ ,但后来我们不能采取任何其他集合,因为它们都重叠了。
但是,我们有:$$ 1 ^ 2 + 2 ^ 2 + 3 ^ 2 + 4 ^ 2 + 5 ^ 2 + 6 ^ 2 + 7 ^ 2=(1 ^ 2 + 2 ^ 2 )+(2 ^ 2 + 3 ^ 2)+(2 ^ 2 + 5 ^ 2)+(2 ^ 2 + 6 ^ 2)+(2 ^ 2 + 7 ^ 2)$$
因此,我们可以得出结论不起作用。