поиск максимальных подмножеств

Question

Для заданного n найдите подмножество S из {1,2, ..., n}, такое, что

1. все элементы S взаимно просты
2. сумма элементов S максимально велика

Поиск грубой силы занимает слишком много времени, и я не могу найти шаблон. Я знаю, что могу взять все простые числа от 1 до n, но это, вероятно, неправильный ответ. Спасибо.

Answer 1

Я бы решил это как проблему динамического программирования . Позвольте мне пройти его в течение 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

Следующее весьма практично.

Пусть N = {1, 2, 3, ..., n}. Пусть p1

Теперь рекурс. S = {1}. Проверьте, является ли pi делителем любого из чисел, уже находящихся в S. Если это так, пропустите Ti. В противном случае выберите число xi из Ti взаимно простого с элементами уже в S и добавьте его в S. Перейти к следующему я.

Когда мы достигнем 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.

Answer 4

Я реализовал рекурсивное решение в Прологе, основанное на взятии списка целых чисел в порядке убывания. На моем довольно древнем ноутбуке Toshiba SWI-Prolog без колебаний выдает ответы для N <90. Вот некоторые моменты времени для N = 100-150 на десятки: </p>

  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 + 1 может быть пропущена, если результат для N известен ранее, поэтому, если диапазон значений 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

Я думаю, что это похоже на проблему подмножества , которая является NP-Complete.

Сначала разбейте каждое число на его простые множители (или используйте список простых чисел для генерацииполный список от 1 до n, тоже самое).

Решите проблему подмножества с помощью рекурсивного спуска, найдя подмножество, не содержащее общих простых чисел.

Выполните все решения и найдите самое большое.