Переборная задача, есть ли шанс?

[Cash]

Есть известная задача: в данном множестве из $N$ элементов найти подмножество с заданной суммой элементов.
Алгоритм следующий: множество разбиваем на две примерно равные части. Например, если дано 44 числа, то на 2 множества по 22 элемента. Для каждой части формируем все подмножества и находим сумму их элементов. Итого у нас получается два массива по $2^{N/2}$ элемента. Сортируем один из массивов. Тогда, пробегая по неотсортированному массиву, мы можем для каждого его элемента найти бинарным поиском в сортированном массиве нужную "добавку", если таковая имеется.
Имея даже не сильно мощный компьютер можно за приемлемое время (несколько минут) управиться со множеством из 50 элементов. 44 элемента потребуют же всего несколько секунд.
А у Вас задача еще несколько проще. Количество элементов искомого подмножества тоже задано. Это сильно сужает перебор.

[Nataly-Mak]

Cash в сообщении #735984 писал(а):

А у Вас задача еще несколько проще. Количество элементов искомого подмножества тоже задано. Это сильно сужает перебор.

Да, у меня задача совсем простая
И я её уже почти решила, осталось всего 5 шагов. Конечно, и эти шаги можно осилить, но уже за бОльшее время. До этого программа работала от нескольких секунд вначале до нескольких минут в конце.
Если описанный вами метод даёт решение за несколько секунд, решите, пожалуйста, задачу и скажите: 11 "правильных" массивов - это окончательный результат

За рекомендации спасибо участникам. К сожалению, воспользоваться ими не могу.

[Cash]

Можете привести задачу полностью?
Во множестве из 44 первых нечетных простых чисел выделить подмножество из 36 элементов с суммой 2628? Правильно?

[Nataly-Mak]

Правильно.

[venco]

Nataly-Mak в сообщении #735988 писал(а):

Если описанный вами метод даёт решение за несколько секунд, решите, пожалуйста, задачу и скажите: 11 "правильных" массивов - это окончательный результат

В эти несколько секунд не входит время на написание программы.

[Nataly-Mak]

Ну да, если бы программа уже была написана, то результат был бы уже в студии

-- Ср июн 12, 2013 20:38:21 --

А тем временем моя программа одолела ещё один шаг:

Начало массива (вариант 5+31):

3  5  7  11  13

Сумма всех чисел в массиве равна 2628.
S1=39, S2=2628-39=2589

 17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  149  157  197 
 17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  149  163  191 
 17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  149  173  181 
 17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  151  173  179 
 17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  157  167  179 
 17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  163  167  173 
 17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  149  151  163  179 
 17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  149  157  163  173 
 17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  139  149  151  167  173 
 17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  131  137  139  149  151  157  173 
 17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  131  137  139  149  151  163  167 

KOLICHESTVO MASSIVOV 11 

Этот вариант программа обрабатывала около часа. Массивов по-прежнему найдено 11.
Осталось всего 4 шага, но самые долгоиграющие.

-- Ср июн 12, 2013 20:55:55 --

venco в сообщении #735996 писал(а):

В эти несколько секунд не входит время на написание программы.

Я свою программу написала за 5 минут:

(Оффтоп)

#COMPILE EXE
#DIM NONE

FUNCTION PBMAIN () AS LONG
 LOCAL I,J,K,Z,W,I1,I2,I3,I4,I5,I6,I7,I8,I9,I10,I11,I12,I13,I14,I15,I16,S,S1 AS LONG
 LOCAL I17,I18,I19,I20,I21,I22,I23,I24,I25,I26,I27,I28,I29,I30,I31,I32,I33,I34,I35 AS LONG
                                                               
Z=39:W=31:S=2589
DIM A(W) AS LONG,P(Z) AS LONG

OPEN "A1.TXT" FOR INPUT AS #1
FOR I=1 TO Z
INPUT #1,P(I)
NEXT I
CLOSE #1

OPEN "A2.TXT" FOR OUTPUT AS #1

K=0
FOR I1=1 TO Z
PRINT "I1=";I1
A(1)=P(I1)
FOR I2=I1+1 TO Z
A(2)=P(I2)
FOR I3=I2+1 TO Z
A(3)=P(I3)
FOR I4=I3+1 TO Z
A(4)=P(I4)
FOR I5=I4+1 TO Z
A(5)=P(I5)
FOR I6=I5+1 TO Z
A(6)=P(I6)
FOR I7=I6+1 TO Z
A(7)=P(I7)
FOR I8=I7+1 TO Z
A(8)=P(I8)
FOR I9=I8+1 TO Z
A(9)=P(I9)
FOR I10=I9+1 TO Z
A(10)=P(I10)
FOR I11=I10+1 TO Z
A(11)=P(I11)
FOR I12=I11+1 TO Z
A(12)=P(I12)
FOR I13=I12+1 TO Z
A(13)=P(I13)
FOR I14=I13+1 TO Z
A(14)=P(I14)
FOR I15=I14+1 TO Z
A(15)=P(I15)
FOR I16=I15+1 TO Z
A(16)=P(I16)
FOR I17=I16+1 TO Z
A(17)=P(I17)
FOR I18=I17+1 TO Z
A(18)=P(I18)
FOR I19=I18+1 TO Z
A(19)=P(I19)
FOR I20=I19+1 TO Z
A(20)=P(I20)
FOR I21=I20+1 TO Z
A(21)=P(I21)
FOR I22=I21+1 TO Z
A(22)=P(I22)
FOR I23=I22+1 TO Z
A(23)=P(I23)
FOR I24=I23+1 TO Z
A(24)=P(I24)
FOR I25=I24+1 TO Z
A(25)=P(I25)
FOR I26=I25+1 TO Z
A(26)=P(I26)
FOR I27=I26+1 TO Z
A(27)=P(I27)
FOR I28=I27+1 TO Z
A(28)=P(I28)
FOR I29=I28+1 TO Z
A(29)=P(I29)
FOR I30=I29+1 TO Z
A(30)=P(I30)
FOR I31=I30+1 TO Z
A(31)=P(I31)

S1=0
FOR I=1 TO W:S1=S1+A(I):NEXT I
IF S1<>S THEN 940

K=K+1
FOR I=1 TO W:PRINT #1,A(I);:NEXT I
PRINT #1,

940 NEXT I31
942 NEXT I30
944 NEXT I29
946 NEXT I28
948 NEXT I27
950 NEXT I26
952 NEXT I25
954 NEXT I24
956 NEXT I23
958 NEXT I22
960 NEXT I21
962 NEXT I20
964 NEXT I19
966 NEXT I18
968 NEXT I17
970 NEXT I16
972 NEXT I15
974 NEXT I14
976 NEXT I13
978 NEXT I12
980 NEXT I11
982 NEXT I10
984 NEXT I9
986 NEXT I8
988 NEXT I7
990 NEXT I6
992 NEXT I5
994 NEXT I4
996 NEXT I3
998 NEXT I2
1000 NEXT I1

2000 PRINT #1,:PRINT #1,"KOLICHESTVO MASSIVOV";K
CLOSE #1
END

END FUNCTION

Тут писать-то нечего. Несколько вложенных циклов и проверка условия.
Дальше просто добавляю ещё один вложенный цикл или наоборот убираю.
И много памяти для моей программы не требуется.

Очень хотелось бы посмотреть на вашу программу, которая решает задачу менее чем за секунду
Какое время требуется на написание такой программы, по вашим прикидкам?

[venco]

Nataly-Mak в сообщении #736000 писал(а):

И много памяти для моей программы не требуется.

Ну да, дурное дело не хитрое.

Nataly-Mak в сообщении #736000 писал(а):

Очень хотелось бы посмотреть на вашу программу, которая решает задачу менее чем за секунду

А что мне за это будет?

Nataly-Mak в сообщении #736000 писал(а):

Какое время требуется на написание такой программы, по вашим прикидкам?

Около 10-ти минут, хотя баги можно долго ловить...

[Nataly-Mak]

venco в сообщении #736013 писал(а):

Nataly-Mak в сообщении #736000 писал(а):

И много памяти для моей программы не требуется.

Ну да, дурное дело не хитрое.

Спасибо за комплимент

Цитата:

А что мне за это будет?

А чего бы вы хотели?

Цитата:

Около 10-ти минут, хотя баги можно долго ловить...

А вот в "дурных" программах багов не бывает

[venco]

Получилось 17 минут.
А программа работает меньше 20 миллисекунд.

-- Ср июн 12, 2013 13:39:18 --

Ну и 11 наборов чисел, которые надо исключать:

 151 163 167 173 179 181 191 193
 151 157 167 173 179 181 193 197
 151 157 163 167 179 191 193 197
 149 157 163 167 181 191 193 197
 149 151 163 173 181 191 193 197
 139 157 167 173 181 191 193 197
 149 151 157 179 181 191 193 197
 137 157 163 179 181 191 193 197
 139 151 167 179 181 191 193 197
 127 163 167 179 181 191 193 197
 127 157 173 179 181 191 193 197

[Cash]

(Оффтоп)

Опередили... Математика на работе - пришлось сортировку самому писать :(. Итого почти час потратил...

Nataly-Mak, Вы правы - 11 наборов всего.

3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+83+89+97+101+103+107+109+113+131+137+139+149+151+163+167
3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+83+89+97+101+103+107+109+113+131+137+139+149+151+157+173
3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+83+89+97+101+103+107+109+113+127+131+137+149+157+163+173
3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+83+89+97+101+103+107+109+113+127+131+139+149+151+167+173
3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+83+89+97+101+103+107+109+113+127+131+137+139+163+167+173
3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+83+89+97+101+103+107+109+113+127+131+137+149+151+163+179
3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+83+89+97+101+103+107+109+113+127+131+137+139+157+167+179
3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+83+89+97+101+103+107+109+113+127+131+137+139+151+173+179
3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+83+89+97+101+103+107+109+113+127+131+137+139+149+173+181
3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+83+89+97+101+103+107+109+113+127+131+137+139+149+163+191
3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+83+89+97+101+103+107+109+113+127+131+137+139+149+157+197

[Nataly-Mak]

venco
Ага, значит, всё-таки 11 массивов и есть.
Спасибо-о-о

А программу не покажете? Вдруг ещё кому пригодится решать подобные задачи.

-- Ср июн 12, 2013 21:50:24 --

Cash в сообщении #736034 писал(а):

Опередили... Математика на работе - пришлось сортировку самому писать :(. Итого почти час потратил...

Не огорчайтесь
И вам огромное спасибо. Ещё раз подтвердили результат.
Теперь могу не сомневаться уже в правильности этого результата.
И свои последние долгоиграющие 4 шага делать не буду

-- Ср июн 12, 2013 22:21:15 --

У меня задач переборных очень много, прямо пачками лежат на столе
Некоторые удаётся решить сразу, другие - сильно подумав, а третьи совсем никак не поддаются.
Например, здесь
post735258.html#p735258
одна из таких задач описана.

Давно она на мне "висит"; бросила тогда, а теперь вот опять она "всплыла". Надо бы сильно подумать

[Nataly-Mak]

Уважаемые коллеги!
Ещё переборная задачка у меня возникла
Пожалуйста, подскажите, с чего начать, как сделать простенькую программку.
Сама немного подумала, но мало Ещё жара, мозги расплавились.

Есть массив простых чисел близнецов, у меня в нём записаны только первые числа из каждой пары близнецов.
Вот начало массива:

3        5       11       17       29       41       59       71 
      101      107      137      149      179      191      197      227 
      239      269      281      311      347      419      431      461 
      521      569      599      617      641      659      809      821 
      827      857      881     1019     1031     1049     1061     1091 
     1151     1229     1277     1289     1301     1319     1427     1451 
     1481     1487     1607     1619     1667     1697     1721     1787 
     1871     1877     1931     1949     1997     2027     2081     2087 
     2111     2129     2141     2237     2267     2309     2339     2381 
     2549     2591     2657     2687     2711     2729     2789     2801 
     2969     2999     3119     3167     3251     3257     3299     3329
. . . . . . 
 

Задача такая:
требуется сформировать несколько первых массивов чисел (для начала штук 10-15), состоящих из 18 пар близнецов (из 36 чисел) таких, что сумма всех чисел массива кратна 6.

Простая задача. Сейчас мозги остужу немного и буду думать.
Жду подсказок

[AV_77]

Если $p$ и $p+2$ - простые близнецы, $p > 3$, то $p + p + 2$ кратно 6. Так что берете любые 18 пар близнецов, кроме пары $(3, 5)$, и получите сумму, кратную 6.

[Nataly-Mak]

Действительно.
Спасибо большое!
И никакой программы воообще не надо.

[Nataly-Mak]

Задача такая возникла... очень долго работает программа, на несколько суток растянется проверка.
Нет ли каких-то идей по оптимизации программы?

Программа проверяет построение примитивного квадрата из 32 пар комплементарных чисел.
Пары комплементарных чисел - это пары чисел с одинаковой суммой (называемой константой комплементарности).
Есть массив, состоящий из 218 пар комплементарных чисел.
Иными словами: массив состоит из двух равных частей A и B таких, что для каждого элемента m из А существует ровно один элемент n в В, что m+n=K.
Для проверки берутся все различные массивы (массивы считаются раличными, если они отличаются по крайней мере одной парой), состоящие ровно из 32 пар комплементарных чисел. Ну, или проверяется сразу весь массив полным перебором.
Понятно, что массивов из 32 чисел будет огромное количество.
И в любом случае проверка очень и очень длинная получается.

Один массив из 32 пар проверяется довольно быстро. Но если бы он был один или хотя бы штук 20-30. Но их будет... я даже не берусь сосчитать сколько.

Можно ли здесь применить многопоточное программирование?
(о котором только слышала, но применять его не умею)

Кто может помочь советом и/или делом

Пример

19  83  1019  1583  3229  3793  4729  4793 
103  167  1103  1667  3313  3877  4813  4877 
499  563  1499  2063  3709  4273  5209  5273 
523  587  1523  2087  3733  4297  5233  5297 
0  0  0  0  0  0  0  0 
0  0  0  0  0  0  0  0 
0  0  0  0  0  0  0  0 
0  0  0  0  0  0  0  0 
S=24024 

Это единственное известное мне решение данной задачи.
Здесь массив состоит из 195 пар комплементарных чисел.
Те элементы, которые здесь нули, это как раз элементы из соответствующей пары, то есть они однозначно определяются 32 найденными элементами квадрата.
Константа комплементарности здесь равна 6006.
S=24024 это индекс примитивного квадрата (S=4K).