gpt4 book ai didi

algorithm - 包含从 1 到 N 的所有数字的最小多集

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:22:55 26 4
gpt4 key购买 nike

假设我们只有整数,其值在 1N 范围内。接下来我们将它们拆分为 K-element 多集。你如何找到这样的集合,其中包含这些多集的最小数量,而这个多集的总和包含从 1N 的所有数字?如果出现歧义,答案将是任何符合条件的集合(首先找到)。

例如,我们有N = 9K = 3

(1,2,3)(4,5,6)(7,8,8)(8,7,6)(1,9,2)(4,4,3)

包含从19的所有数字的最小多集数等于4,可以是 (1,2,3)(4,5,6)(7,8,8)(1,9,2)(1,2,3)(4,5,6) (8,7,6)(1,9,2)

找到这样的集合的高效算法有什么想法吗?

附言写完答案后,我发现了另一个 4 元素集:(4,5,6)(1,9,2)(4,4,3)(7,8,8) (4,5,6)(1,9,2)(4,4,3)(8,7,6) 但正如我所说,找到任何最小集的算法会没事。

最佳答案

你的问题是经典的限制版Set Covering problem , 但仍然很容易证明它是 NP-Hard .

此问题的任何近似技术在这里都是合理的。特别是 greedy solution选择覆盖最多未发现项目的下一个子集 - 尤其是。易于实现。

关于algorithm - 包含从 1 到 N 的所有数字的最小多集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30788361/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com