algorithm - 寻找最大子集

Question

对于给定的 n，找到 {1,2,...,n} 的子集 S 使得

1. S的所有元素互质
2. S的元素之和尽可能大

进行强力搜索需要太长时间，我找不到模式。我知道我可以只取从 1 到 n 的所有素数，但这可能不是正确的答案。谢谢。

Answer 1

我会将其作为 dynamic programming problem 处理.让我走一遍 20。首先以相反的顺序取素数。

19, 17, 13, 11, 7, 5, 3, 2

现在我们将逐步讨论使用了那些大小不断增加的素数的子集的最佳解决方案。我们将进行广度优先搜索的变体，但我们始终使用最大的当前未使用的素数(可能还有更多)。我将以 size: {set} = (total, next_number) 的形式表示所有数据结构。 (我是手工做的，所以所有的错误都是我的。)下面是我们如何构建数据结构。 (在每一步中，我都会考虑从上一步中增长所有更小尺寸的集合的所有方法，并取最好的总和。)

尝试重现此 list ，并以我犯的任何错误为模，您应该有一个算法。

Step 0
0: {} => (1, 1)

Step 1
1: {19} => (20, 19)

Step 2
2: {19, 17} => (37, 17)

Step 3
3: {19, 17, 13} => (50, 13)

Step 4
4: {19, 17, 13, 11} => (61, 11)

Step 5
5: {19, 17, 13, 11, 7} => (68, 7)

6: {19, 17, 13, 11, 7, 2} => (75, 14)

Step 6
6: {19, 17, 13, 11, 7, 5} => (73, 5)
   {19, 17, 13, 11, 7, 2} => (75, 14)

7: {19, 17, 13, 11, 7, 5, 2} => (88, 20)
   {19, 17, 13, 11, 7, 5, 3} => (83, 15)

Step 7
7: {19, 17, 13, 11, 7, 5, 2} => (88, 20)
   {19, 17, 13, 11, 7, 5, 3} => (83, 15)

8: {19, 17, 13, 11, 7, 5, 3, 2} => (91, 18)

Step 8
8: {19, 17, 13, 11, 7, 5, 3, 2} => (99, 16)

现在我们只需向后跟踪数据结构以读取 16, 15, 7, 11, 13, 17, 19, 1 我们可以对其进行排序以获得 1, 7, 11、13、15、16、17、19。

(请注意，有很多细节可以正确地将其转化为解决方案。祝你好运!)