找到最大的子集

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