Есть такая неприятная (для меня) задачка. Уже неделю бьюсь  - никак не могу придумать как эффективно решить.
Есть ряд целых чисел a1 - aN  и ряд целых чисел W1 - WN. Числа из ряда W1-WN являются суммами чисел а1-аN. Необходимо найти какие числа из ряда а1-аN являются членами каких чисел из ряда W1 - WN. Необходимо найти первый подходящий вариант
например
ряд чисел 1 1 4 5 6 и второй ряд чисел 6 11. Решением может быть как 6 = 1 + 1 + 4 и 11 = 5+6 так и 6 = 6 и 11 = 1+1+4+5
хоть пните куда читать...

http://yandex.ru/yandsearch?clid=9582&text=задача+о+рюкзаке&lr=213

Вы не полностью описали условия задачи поэтому - (1)

а какое еще требуется описание?

Числа первого ряда(А) должны быть все использованы во втором ряде(W)?
если да то я бы решил примерно так
1. Цикл n по W
2. найдем все варианты(V) решения рюкзака W1
3. для каждого V будем подбирать из оставшихся А Для W2... и так далее
4. если нельзя вычислить ровно на этапе 3, то такой вариант убираем.

про рюкзак как написано в вики и большинстве источников мне не нравится.
вот
http://discopal.ispras.ru/Задача_о_рюкзаке:жадный_алгоритм
http://discopal.ispras.ru/Задача_о_рюкзаке:PTAS
http://discopal.ispras.ru/Задача_о_рюкзаке:динамическое_программирование

(4) да все числа первого ряда должны быть использованы во втором.
читаю ссылки

Вы не описали целевую ф-цию

(6) не совсем вас понимаю. Но если рассматривать данную задачу в классической постановке задачи о рюкзаке, то стоимость чисел равна их величине и  необходимо найти оптимальное решение.

первый подходящий противоречит - оптимальному решению.

почему? первый подходящий вариант и будет одним из оптимальных решений?

задача о рюкзаке лет 15 как есть в программах изучения всех специальностей связанных и ит.

я признаю что я плохой программист. Собственно поэтому и обращаюсь на форум - может тут  помогут.

первый ряд 1, 3 второй 2, 2 - задача не имеет решения
а вообще динамическое программирование решает проблему

На самом деле, как показала практика, то с примерно 10-20 чисел наиболее удачным способом подбора суммы является случайный выбор - один массив из всех чисел - с плавающей границей.
Нижняя часть массива - тестовая сумма (от начала до границы).
Если тестовая сумма больше чем надо - то выбираем любой элемент от начала и до границы, переносим его на границу (при этом тот, который был на границе, отправляется на его место - то есть SWAP) и смещаем границу вниз на один элемент (ну и в начало).
Если тестовая сумма меньше чем надо - то выбираем любой элемент больше границы и до конца - ставим его следующим на границу (то есть опять делаем SWAP) и смещаем границу на один вверх (ну и в начало).
Если сумма совпала - то выходим.
Подбирает быстро и хорошо - проверяйте (если, конечно в 1С есть случайное число - я на "Васике" писал - там всё есть).

(12) задача заранее имеет решение - числа из ряда 2 были получены сложением каких то чисел ряда 1

(13) ща подумаем

исчерпывающий рекурсивный перебор до первого правильного решения

Цифра N она приблизительно какая?

в случае ряда W1 - WN - в пределах десяти
в случае ряда a1 - aN - в пределах тысячи

(18) >в случае ряда a1 - aN - в пределах тысячи

Тупой перебор займет тысячелетия. Вариантов 2 ^ 1000

Ладно было бы в пределах 10-20

"При этом элементарные познания в математике и критическое мышление как бы должны натолкнуть на мысль, что уже на десятом складывании листа, слоёв выходит 1024, а при следующем ? в два раза больше и так далее. Случись, какому-то кузнецу-задроту действительно сложить металл тысячу раз, предполагаемое количество слоев было бы равно 21000 = 1,07e+301 (10301), что, на секундочку, превышает количество атомов в тех ~5 мм толщины лезвия меча, всём мече, его хозяине, земле, солнечной системе и во всей обозримой вселенной, равное всего каким-то 1080 (10 и ещё 79 нулей сзади). "(С)

(19) Нормально решается рюкзак на тысяче значений.
Простым направленным перебором с отсечениями.

(21) Так я и говорю про тупой перебор.

(12) А какое отношение динамическое программирование имеет к задаче о рюкзаке, и к задаче в (0) - которая является тоже чистой задачей о рюкзаке, только ему по-очереди нужно подбирать разные значения суммы.
(22) Ну или Симплекс, что по сути тоже перебор.

(21) дык. Это если один. и если нас устраивают неоптимальные решения. а мне надо фактически произвести дезагрегацию итогов.
Я вообще почитал тут интернеты, и осознал что вообще эта задача скорее про подсуммы. Легче от этого правда не стало

(22) Несколько секунд написанный на 1С-ке занимает как правило перебор на тысяче значений.

(25) но это для одного значения. А нам то надо чтобы все числа из ряда 1 влезли в ряд два. То есть вполне может оказаться что нам сначала надо получить все варианты для первого числа, потом для каждого из этих варинатов посчитать варианты для второго числа и так далее.
короче это все безумие. Руководство просто с ума сошло - система будет висеть а сэкономим копейки...

(26) Это тоже задача о рюкзаке. Конечно сложность возрастает, но не так страшно. А сколько значений в первом, и сколько во втором ряду?
Какая погрешность допустима, или нужно выходить на суммы копейка-в-копейку?

(27) копейка в копейку
первый ряд порядка до тысячи, второй ряд до 10

(28) А откуда они знают что сумму можно набрать копейка в копейку?
Вообще - нормально можно считать подряд.
Перебираешь начиная с больших значений, и подбираешь начиная с максимальных.
На практике будет нормально работать

потому что

извиняюсь
потому что суммы ряда 2 были получены путем сложения чисел из ряда 1. Это заранее известно

(30) см. (29)
нормально будет работать.
Переборный рюкзак с отсечениями начиная с больших значений - я где-то выкладывал. Должен быть в поиске.

ща буду искать
блин как люди до таких знаний дорастают(((

(33) Не то пишу. С левого ряда нужно перебирать начиная с больших, а вот подбираемые, с правого - начиная с меньньших к большим.
Отсечений можно сделать много, но на практике достаточно отсекать если оставшаяся сумма меньше набранной плюс минимальное оставшееся значение, и если набранная сумма больше необходимой. Можно сделать отсечение если сумма всех оставшихся меньше меньше необходимой до добора суммы.
Одинаковые значения с левого ряда нужно группировать в пул.

(34) я пока что пытаюсь протестить ваш код из Подскажите алгоритм на 100 значения, 30 суммируемых значениях и одном числе. НО спасибо за наводку

(35) Это не тот вариант. Это без отсечений, без группировки одинаковых пул, и безз перебора начиная с больших.

(35) http://abelov.com/kuban/139872.html#11 этот конечно ближе но я хочу сначала простой вариант проверить. все таки в абапе это чуточку по другому выглядит - надо понять как компилятор работает с рекурсией.

Нужен алгоритм набора нужной суммы
Вот тут правда тоже недоделок - не переписано под массив, и не все отсечения. И задача не подбора точной суммы.

(0) Можно попробовать такой подход (кратко саму идею). Для не слишком большого числа W может оказаться реализуемым.
Если правильно понял, задача формально выглядит как поиск решения системы линейных уравнений с булевыми переменными (специального вида):
СУММА(i,j)Ai*Xij=Wj, Xij = {0,1} Xij = 1, если число Ai входит как слагаемое в число Wj (i = 1..N, j = 1..M).
Рассмотрим такую функцию (производящая функция числа решений системы уравнений):
F(Zj) = ПРОИЗВЕДЕНИЕ(i,j)(1+Zj^Ai).
Если в F(Zj) произвести умножение и привести подобные члены, т.е. представить ее в виде полинома:
F(Zj) = СУММА(k1,k2..)C(k1,k2..)*Z1^k1*Z2^k2*...
то коэффициент C(W1,W2..) - число решений системы.
Приведение F(Zj) к "нормальному" виду можно делать последовательно раскрывая скобки и приводя подобные члены. Так что число операций будет порядка N*СУММА(Ai). При этом, т.к. нужно получить лишь одно решение, процесс можно оборвать, как только получится 1 для заданных правых частей системы (W1,...,WM).

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

wiki:Задача_о_рюкзаке

(40) Ничего подобного. Задача где каждый предмет не уникальный, а его можно брать неограниченное число раз - можно решить методами динамического программирования. Тут нет такой задачи.

Причем метод динамического программирования по отношению к стандартному рюкзаку.

(41) не понимаю принципиальной разницы в данном случае

(43) объясняю - методами динамического программирования задача (41) сводится к обычновенному рюкзаку. Который методами динамического программирования не решается.

(42) Мне тоже кажется, что динамическое программирование, как общий метод, годится для всего и может свестись к полному перебору.

(44) ну это смотря что иметь ввиду под динамическим программированием

(44) Да, но обычно динамическим программированием называют методы которые позволяют уйти от полного перебора путем сохранения промежуточных значений при решении подзадачи.

Честно решить задачу в (0) можно при помощи Гомори.

(44) Динамическим программированием называют методы, основанные на принципе Беллмана: "Часть оптимальной траектории - оптимальна". Но, по сути, это терминологические заморочки, к сути (трудоемкость) не имеющие отношения.
2 Ненавижу 1С: жду и никак не дождусь Вашего комментария к (39).

(49) Я торможу, никак не могу в него въехать.
//
Вообще, в правой части N членов, в левой M
получаем NxM неизвестных Aij, каждое принимает значение 0 либо 1. (можем добавить NxMx2 неравенств <=0 и >=0),
имеем M равенств, и суммы Ai должны быть равны единице (еще N равенств)
И дальше Гомори.

(49) сплю что-то
еще должны быть условия
СУММА(j)Xij=1 - входит только в одно

(51) Т.е. обязательно входит в одну из сумм?
Формально в производящей функции удвоится число переменных и добавятся сомножители вида (1+Zk) (k=M+1..2M). Трудоемкость увеличится на N*M.
Для уравнения X1+X2+...+Xn = W, производящая функция F(Z)=(1+Z)^n. В "нормальном" виде это бином Ньютона и число решений - биномиальные коэффициенты. Если раскрывать скобки и приводить подобные члены, то трудоемкость примерно n^2. Так же и в общем случае: N*сумму всех коэффициентов.
Поэтому, для задач с "ограниченными" коэффициентами может сработать.

(52) У него сумма Ai равно сумме Wi

(53) Если каждое число обязательно куда-то входит по одному разу, то да (похоже на комбинаторные блок-схемы).
А что это меняет?

(54) Мы имеем M+N линейных уравнений с M*N целочисленных неизвестных принимающих значение 0 или 1. (между нулем и единицей)
Больше ничего лишнего в условии нет.

(55) Все, понял. Тупеешь в период закрытия квартала.

(56) Получаем решение неоднородной системы уравнений, дальше приводим решение к базису. Или я тоже туплю?

В случае СУММА(j)Xij=1 производящая функция числа решений будет иметь такой вид (явно учтено, что Ai обязательно входит только в одно Wj):
F(Z1,...,Zm) = ПРОИЗВЕДЕНИЕ(i)(Z1^Ai+Z2^Ai+...+Zm^Ai).
А дальше раскрывать скобки и приводить подобные члены. В результирующем полиноме членов не более СУММА(Ai), значит и трудоемкость будет примерно такой.

Я так и не понял - почему нельзя просто решить систему линейных уравнений?

(59) Переменные - 0 или 1, уравнений меньше, чем переменных.
Как Вы собираетесь ее решать? В общем случае это NP-полная задача.

(60) То есть как? Решение неоднородной системы линейных уравнений это NP-полная задача?!

Сейчас на примере из ноль распишу.

Уравнение -
1 0 0 0 0 1 0 0 0 0   1
0 1 0 0 0 0 1 0 0 0   1
0 0 1 0 0 0 0 1 0 0   1
0 0 0 1 0 0 0 0 1 0   1
0 0 0 0 1 0 0 0 0 1   1
1 1 4 5 6 0 0 0 0 0   6
0 0 0 0 0 1 1 4 5 6   11

(63) И что с (63) Вы предлагаете делать?

(64) У меня вообще голова не варит.
Я уж забыл что я хотел.
Решаем неоднородную систему, а потом выходит перебор свободных членов :(

(65) Что-то меня все игнорируют. Для примера в (0) производящая функция числа решений будет такая:
F(Z1,Z2) = (Z1+Z2)(Z1+Z2)(Z1^4+Z2^4)(Z1^5+Z2^5)(Z1^6+Z2^6).
Почему бы не раскрыть скобки и привести подобные члены?

(66) Раскрыли скобки, а дальше?

(66) Само раскрытие скобок по ресурсоемкости разве не равно полному перебору?
В общем случае у нас число членов получится 2^N, Для подбора двух сумм.

А нет, О(N)

А вот теперь я соображаю :)
Решив систему неоднородных уравнений, выведя свободные члены -
Мы можем систему равенств превратить в систему неравенств
Так как каждое неизвестное >=0 и <=1
Теперь при переборе свободных членов можно максимизировать отсечения.
В процессе перебора, зная текущие значения свободных членов можно вычислить максимально и минимально возможные значения выражения. И если минимальное больше единицы, или максимальное меньше нуля - то ветвь отсекаем.

И вообще сначала проходом можем вычислить фиксированные значения, которые не надо проверять.
А затем уже перебирать.
Для примера
1,2,5,7. Подбираем 6 и 9

x1 =   2 x6 + 5 x7 + 7 x8 - 8  
x2 =  - x6 + 1  
x3 =  - x7 + 1  
x4 =  - x8 + 1  
x5 =  - 2 x6 - 5 x7 - 7 x8 + 9  
x6, x7, x8 - свободные переменные.
Из первого уравнения x8=1, x7=0, x6=1
Соответственно x1=1
x2=0
x3=1
x4=0
x5=0
то есть 1(x1)1+0(x2)2+1(x3)5+0(x4)7 = 6

матрица была
10001000 1
01000100 1
00100010 1
00010001 1
12570000 6
00001257 9

Проверить решение можно тут
http://www.math-pr.com/equations_1.php

Короче - нужна компонента для решения разряженной системы неоднородных линейных уравнений.
И после её использования уже можно делать нормальный перебор.

Есть оказывется методы решения неравенств в целых числах. Например метод фурье-моцкина.

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

чувствую себя мелким муравьем...

(76) зато в соседней теме ты крут

имхо надо сначала одиночные совпадения из ряда 1 и ряда 2, а потом уже тупо перебирать, и какая разница что во втором ряду и 6 и 11 подходят, если это в условиях не прописано (как например 11 и 11, первую брать или вторую)

+ исключить

(0) Готов сделать как в (39), (58). Только подтвердите, что это действительно нужно. Мыло в профиле.

(80) В (39) и (58) 100% ошибка как минимум в сложности алгоритма.
Сумма чисел слева равна сумме чисел справа. Поэтому второе условие мы можем убрать и получаем чистый рюкзак.
Насчет динамического программирования вспомнил - оно применяется при небольшой дискретной вместимости ранца.
Сложность алгоритма решения тогда О(количество_Предметов*вместимость_ранца)

(81) Сложности не вижу. Обычно (было уже раза 4) после предложения топикстартеру поковыряться с задачей обращений нет. Видимо, задача не слишком актуальна или возможны другие подходы.

(82) N*СУММА(Ai) - действительно похоже на правду. Такую-же сложность даст решение динамическим программированием.

Хотя что-то не то я нашел. Динамическим программированием экспоненциальна сложность решения. У нас все наборы хранятся. А их экспоненциальное количество.
То есть сложности указанной в (39) Быть не может.
Такая сложность только если мы каждый предмет можем брать неограниченное число раз.

Сделал в 1С как в (58). Немного погонял, итги неутешительные: для N=1000 и М=10 работать вряд ли будет.
100х2: 1 сек.
150х2: 1 сек.
200х2: 2 сек.
250х2: 2 сек.
300х2: 3 сек.
350х2: 5 сек.
400х2: 6 сек.
450х2: 8 сек.
500х2: 10 сек.
1000х2: 39 сек.

100х3: 25 сек.
150х3: 87 сек.
200х3: 201 сек.
250х3: 404 сек.
300х3: 699 сек.

100х4: 1 081 сек.
Сложность O((N*M)^2). Основное время тратилось на построение ключа для монома Z1^k1*...*ZM1^kM.

(85) Ну не может рюкзак с такой сложностью решаться.
А в (0), при двух набираемых суммах - чистый рюкзак.

Проврался с трудоемкостью в (85): O(N^M). Трудоемкость определяется количеством членов в полиноме (58), оно порядка числа решений K1+...+KM = N - это полиномиальный коэффициент, т.е. O(N^M).
(86) Согласен (если решать, как в (58) можно M увеличить на 1, но не более), но для M=2 и в (58) получается O(N^2), а это приемлимо.
В общем, для характеристик в (0) (N=1000, M=10) этот метод не сработает.