(метод Гомори) Помогите какой алгоритм выбрать

[VanLeo]

Такая вот задача:
Есть массив чисел (предположим "1,2,3,4,5") и несколько целевых параметров (предположим "3 и 9").
Суть задачи: необходим алгоритм, который бы перебирал массив таким образом, чтобы
1. сумма отобранных элементов массива был равен целевому параметру, т.е. 1 + 2 = 3.
2. отобранные элементы исключаются из массива (чтоб одни и те же элементы не учитывались при расчете для более одного целевого параметра), а для оставшихся (3,4,5) снова проводился отбор, чтобы получить число 9: 4+5=9.

Прошу подсказать в направлении анализа, может формула уже есть, а напишу я сам. 

[Алексей++]

считать придётсям перебором сочетаний. Когда найдено нужное сочетание, запоминаем куда нибудь, а числа удаляем из массива (например, заменить там числа "невалидными значениями", которые никогда в алгоритме не учавствуют, либо "сжать" массив, удалив числа)

и по новой искать начинаешь

[Алексей++]

перебор сочетаний , имхо, удобно производить при помощи длинного двоичного числа:
если массив имеет N байт, то "двоичный" массив будет (N+8)/8 байт .
Биты двоичного массива будут показывать, какие числа сейчас в наборе (единичные биты соответствуют позиции цифры в главном массиве).
Ну а перебор сочетаний сводится к инкреминированию длинного двоичного числа - это уже не так сложно

[Sands]

Алексей1153++, Перебор сочетаний вещь хорошая, но если сразу удалять числа, то по идее можно нарваться на ситуацию, когда некоторое число нельзя будет "собрать".
В приведенном примере все хорошо, а вот если на наборе "1,2,3,4,5" предложить собрать параметры 6 и 8, тогда перебором первое подходящее для 6 буде 5 и 1, а после их удаления из 2, 3, и 4 8 мы никак не получис, хотя если из базового выбрать сначала 2 и 4 для 6, то из 3 и 5 мы получим 8.
Или ты имел ввиду перебор с откатами?

[Алексей++]

Sands, соответственно, счётчики сочетаний надо с нуля пускать

сжимать массив полезно, кстати, будет ) Когда много искать наборов. А если немного - просто на невалидные значения менять

[Алексей++]

Sands, аа, я понял, про что ты , ага, придётся с откатами

[Sands]

И все таки интересно, может реально сюда многокритериальную оптимизацию в целых числах прикрутить. Тогда метод Гомори применить и получить результат?

[Алексей++]

что за метод такой ? )

[Sands]

Алексей1153++, Ну если искать максимум функции на некоторой непрерывной области в RxR, тогда можно применять Симплекс-метод, ну или другие, а вот если имеем дискретную одбласть(как в данном случае), тогда задачу решают методом Гомори(их аж 3). Навскидку я их не приведу, но тут просили дать направление поиска, вот я и даю ))
ЗЫ RxR тут использовано для примера. В общем случае, конечно же имеем R^n

[Sands]

Пусть x1,x2,...xN - ето числа в массиве, а b1,b2,...,bM - это множество целевых параметров
тогда можно записать следующее

a11*x1+a12*x2+...+a1N*xN = b1
a21*x1+a22*x2+...+a2N*xN = b2
.............................
aM1*x1+aM2*x2+...+aMN*xN = bM

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

a11+a21+...+aM1 <= 1
a12+a22+...+aM2 <= 1
...................
a1N+a2N+...+aMN <= 1

"меньше или равно" здесь использовано потому, что как видно из примеров некоторые цифры могут вообще не использоваться ни в одной сумме
и еще к етому всему добавятся условия

aij >= 0 i = 1..M, j = 1..N

А критерий максимизации будет иметь вид

(a11+a21+...+aM1)*x1+(a12+a22+...+aM2)*x2+...+(a1N+a2N+...+aMN)*xN -> max

ну и решать ето все в целых числах, понятно, что относительно

aij i = 1..M, j = 1..N

[Алексей++]

Excel, в принципе, сможет решить такую задачу

в экселе, правда, придётся попотеть над организацией задания условий для поиска решения, ну а решит он в момент

[Sands]

Алексей1153++, Да, задание условий - ето небольшая проблема, бОльшая проблема в том, что данный метод не дает гарантий правильности результата, потому как на практике он мной не опробован, ибо придуман был совсем недавно ))
В связи с етим может получиться, что автор темы потратит время, а результата не достигнет. Потом будет расстраиваться.
Я б на его месте сходил бы с етой идеей к преподавателю(если ето задача учебная), а если рабочая - тогда брейнсторм на работе с коллегами.

[sam_]

можно каким-нибудь образом решить задачу методом Гомори в другой среде? допустим matlab