找到最大的子集

Question

对于给定的n，发现{1,2，...，N}，使得

1. S的所有元素的子集S是互质
2. S的元素的总和是尽可能大的

做一个蛮力搜索需要很长时间，我找不到一个模式。我知道我可以从1到n取所有素数，但这可能不是正确的答案。谢谢。

Answer 1

我会解决这个作为dynamic programming problem。让我步行穿过它20.首先以相反的顺序进行素数。

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

现在我们打算走到这已经使用尺寸增加的那些素数的子集的最佳解决方案。我们将做一个变化的广度优先搜索，但是我们总是使用最大的当前未使用的素数（加上可能更多）。我将以size: {set} = (total, next_number)的形式表示所有数据结构。 （我手工操作，所有的错误都是我的。）以下是我们如何构建数据结构。 （在每一步中，我会考虑从上一步增加一组较小尺寸的所有方法，并采取最佳总计。）

尝试重现此列表并重新模拟我制作的任何错误，您应该有算法。

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。

（注意，有一个很多的细节，以得到正确的把它变成一个解决方案。祝你好运！）

Answer 2

你可以通过获取素数的能力来做更好的事情，达到你的约束。例如，假设n = 30。然后你想开始

1, 16, 27, 25, 7, 11, 13, 17, 19, 23, 29 

现在看看有哪些地方需要改进。当然，你不能增加任何已经至少n/2的素数：17,19,23,29（为什么？）。另外，3^3和5^2接近30，所以它们也可能是最好的独立（为什么？）。

但是2^4,7,11和13呢？我们可以采取2，并且带有7将它们结合起来，11或13。这将使：

2 * 13 = 26 replaces 16 + 13 = 29 BAD 
2 * 11 = 22 replaces 16 + 11 = 27 BAD 
2^2 * 7 = 28 replaces 16 + 7 = 23 GOOD 

所以看起来我们应该得到下面的列表中（现在排序）：

1, 11, 13, 17, 19, 23, 25, 27, 28, 29 

尝试证明这是无法改进的，这应该让你对一般情况有所了解。

祝你好运！

Answer 3

我认为这与NP-Complete的subset problem相似。首先，将每个数字分解为其主要因素（或使用素数列表从1到n生成完整列表，同样的事情）。

通过找到不包含公共素数的子集来解决递归下降的子集问题。

运行所有解决方案并找到最大的解决方案。

Answer 4

我实现了在序言递归解决方案的基础上，采取以降序整数列表。在我的相当古老东芝笔记本电脑，SWI-Prolog的产生答案毫不犹豫地对于N < 90.下面是一些定时为N = 100至150，以几十：

N   Sum  Time(s) 
----- --------- ------- 
100  1356   1.9 
110  1778   2.4 
120  1962   4.2 
130  2273  11.8 
140  2692  16.3 
150  2841  30.5 

定时反映从头开始每个的实施N的值。如果N的结果是先前已知的，则可以跳过N + 1的很多计算，因此如果要计算值N的范围，则利用该值是有意义的。

序言源代码如下。

/* 
    Check if two positive integers are coprime 
    recursively via Euclid's division algorithm 
*/ 
coprime(0,Z) :- !, Z = 1. 
coprime(A,B) :- 
    C is B mod A, 
    coprime(C,A). 

/* 
    Find the sublist of first argument that are 
    integers coprime to the second argument 
*/ 
listCoprime([ ],_,[ ]). 
listCoprime([H|T],X,L) :- 
    ( coprime(H,X) 
    -> L = [H|M] 
    ; L = M 
    ), 
    listCoprime(T,X,M). 

/* 
    Find the sublist of first argument of coprime 
    integers having the maximum possible sum 
*/ 
sublistCoprimeMaxSum([ ],S,[ ],S). 
sublistCoprimeMaxSum([H|T],A,L,S) :- 
    listCoprime(T,H,R), 
    B is A+H, 
    sublistCoprimeMaxSum(R,B,U,Z), 
    ( T = R 
    -> (L = [H|U], S = Z) 
    ; (sublistCoprimeMaxSum(T,A,V,W), 
      ( W < Z 
      -> (L = [H|U], S = Z) 
      ; (L = V, S = W) 
     ) 
     ) 
    ). 

/* Test utility to generate list N,..,1 */ 
list1toN(1,[1]). 
list1toN(N,[N|L]) :- 
    N > 1, 
    M is N-1, 
    list1toN(M,L). 

/* Test calling sublistCoprimeMaxSum/4 */ 
testCoprimeMaxSum(N,CoList,Sum) :- 
    list1toN(N,L), 
    sublistCoprimeMaxSum(L,0,CoList,Sum). 

Answer 5

以下是非常实用的。

设N = {1，2，3，...，n}。 设p1 < p2 < p3 < p3 < pk是N中的质数 设Ti为N中可被pi整除的自然数，但不小于pi的任何素数。 我们可以从每个子集中挑选至多一个数字Ti。

现在递归。 S = {1}。 检查pi是否是S中任何数字的除数。如果是，则跳过Ti。 否则，从Ti coprime中选择一个数字xi到已经在S中的元素，并将其添加到S. 转到下一个i。

当我们到达k + 1时，计算S中元素的总和。如果有新的最大值，则将S保存起来。

继续。

取N = 30。 的素数是2，3，5，7，11，13，17，19，23，和29。

T1 = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30} 
T2 = {3, 9, 15, 21, 27} 
T3 = {5, 25} 
T4 = {7} 
T5 = {11} 
T6 = {13} 
T7 = {17} 
T8 = {19} 
T9 = {23} 
T10 = {29} 

所以少于15 * 5 * 2 = 150种可能性。

这里是n个我原来的错误的结果= 100

1 17 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 88 89 91 95 97 99 
Sum = 1374 

应该

1 17 23 29 31 37 41 43 47 53 59 61 67 71 73 79 81 83 88 89 91 95 97 
Sum = 1356 

小于2秒，其中n = 150约9秒，其中n = 200