Подбор суммы из набора чисел - помогите оптимизировать алгоритм

Имеется:
Массив из 96 элементов
Каждый элемент - число от 1 до 1.000.000 определенное рандомом
Сумма всех елементов массива приблизительно 13000000

Необходимо:
Сделать выборку из любого количества элементов, сумма которых равна заданой
Заданая сумма приблизительно равна 2500000

Методом тупого перебора придется перебрать 2^96 комбинаций
На 3ГГц процессоре, при условии что за один такт будет определяться одна комбинация для перебора всех комбинаций потребуется приблизительно 9*10^24 дней - за такой промежуток времени Земля перестанет существовать...

Найденые решения:

Просуммировав максимальные значения из массива определить минимальное количество элементов в комбинации
Просуммировав минимальные значения из массива определить максимальное количество элементов в комбинации

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

Вобщем, буду рад любым идеям.

Сообщение отредактировано: white_ng - 25.09.07, 17:10

white_ng
Тебе понадобится массив A длиной, равной необходимой сумме. i-й элемент массива означает, что мы можем набрать сумму, равную i.
Сначала A[0]=1, а все остальные равны нулю. Потом в цикле мы берем очередное число и для всех ненулевых элементов помечаем новые. Примерно это выглядит так:

for i := 1 to 96 do
  for j := sum-C[i] downto 0 do
    if A[j]<>0 then A[j+C[i]]=1;

И в конце, если A[sum]<>0, то данную сумму можно набрать. Чтобы узнать, как именно она набирается, нужно для каждого ненулевого A[i] запоминать, какой элемент массива C был использован.

ЗЫ. Это все называется метод динамического программирования. Сложность данного алгоритма O(sum*sizeof( C )). В твоем случае это примерно 2500000*96=240 млн. операций => меньше секунды работы компьютера.

Сообщение отредактировано: Pacific - 25.09.07, 19:50

Цитата Pacific @ 25.09.07, 19:47

white_ng
Тебе понадобится массив A длиной, равной необходимой сумме. i-й элемент массива означает, что мы можем набрать сумму, равную i.
Сначала A[0]=1, а все остальные равны нулю. Потом в цикле мы берем очередное число и для всех ненулевых элементов помечаем новые. Примерно это выглядит так:

for i := 1 to 96 do
  for j := sum-C[i] downto 0 do
    if A[j]<>0 then A[j+C[i]]=1;

И в конце, если A[sum]<>0, то данную сумму можно набрать. Чтобы узнать, как именно она набирается, нужно для каждого ненулевого A[i] запоминать, какой элемент массива C был использован.

ЗЫ. Это все называется метод динамического программирования. Сложность данного алгоритма O(sum*sizeof( C )). В твоем случае это примерно 2500000*96=240 млн. операций => меньше секунды работы компьютера.

А с чего вы взяли что числа целые?

esperanto
Если они не целые, то задача NP-полная И автор топика в этом случае может начать придумывать эвристики. А так у него есть хотя бы один эффективный алгоритм.

Цитата Pacific @ 25.09.07, 20:17

esperanto
Если они не целые, то задача NP-полная И автор топика в этом случае может начать придумывать эвристики. А так у него есть хотя бы один эффективный алгоритм.

Если ваше решение и правильное оно все равно имеет экспоненциальную сложность по времени и по памяти.

Но конечно лучше чем перебор

esperanto
Я написал, какую сложность имеет этот алгоритм. Фактически (при грамотной реализации) она равна количеству различных сумм, которые можно получить, помноженному на размер массива C. И в случае нецелых чисел становится равна C*2^C. Но если у него целые числа, то алгоритм достаточно эффективен. Вообще, это стандартная техника динамического программирования. А задача эта широко известна и называется "задача о сдаче с доллара".

Сообщение отредактировано: Pacific - 26.09.07, 04:55

А также как "задача о ранце (рюкзаке)".

Сообщение отредактировано: Pacific - 26.09.07, 06:00

2 Pacific

Спасибо, супер! Будем юзать.

Сложность для РС конечно повыше, но всеравно премлемая.

Необходимо только обойти нюансы.

1.

Допустим, на первой итерации когда массив А почти пустой берем первое число. допустим это 100. добавляется 0+100=100, А[100]=1

на второй итерации нужно добавить 110.
A[0]=1, 0+110=110, ок добавляем A[110]=1
дальше A[1]...A[99]=0, ниче не добавляем
A[100]=1, 100+110=210, добавляем A[210]=1

Но теперь, следующее ненулевое число - только что добавленое A[110]=1. Не будешь ведь добавлять еще и 110+110=220, A[220]=1, правильно?
Ведь каждый элемент может использоваться 1 раз.

Для этого нужно иметь еще один массив с количеством элементов равным сумме в который будут записываться элементы, которые нужно добавить в А на каждой итерации.

2.

Теоретически возможно для каждой из сумм несколько вариантов составления, например 0+250=250, и 120+130=250
Кроме того, в исходном массиве могут быть одинаковые числа.

Думаю, вместо одномерного массива А можно создать двухмерный массив суммаХ96 куда в каждую строчку для каждой итерации будут записываться номера строчек из которых можно попасть в него на даной итерации, а если нельзя - то -1

***********************************************************************************************************

2 esperanto

Числа целые. Сначала они были дробными, но значение имеют только первые два знака, так что после умножения на 100 они превратились в целые.

Цитата white_ng

не будешь ведь добавлять еще и 110+110=220, A[220]=1, правильно?

Естественно, для этого как раз внутренний цикл в алгоритме проходится в обратном направлении. В результате, в 1 выставляются уже пройденные элементы, и ничего лишнего не добавляется. Массив сумма*96 не нужен, достаточно обойтись одномерным массивом. Только выставлять не единицу, а число от 1 до 96, обозначающее, что именно было использовано.

Добавлено 26.09.07, 08:31
Только этот алгоритм позволяет найти какой-то один способ набрать нужную сумму. Если тебе нужно найти все способы, придется делать двумерный массив, который ты описал, и потом его рекурсивно обходить, начиная с элемента A[sum,96].

2 Pacific

ок.
Завтра постну окончательное готовое решение когда сделаю.

2 All

Задачу можно считать решенной

Всем спасибо.

Цитата Pacific @ 26.09.07, 04:54

Но если у него целые числа, то алгоритм достаточно эффективен.

В теории эффективныи называют полиномиальные алгоритмы, а ваш экспоненциальный.

Сложность алгоритма определяется как функция длины входных данных.

-Added 26.09.07, 09:14

Цитата Pacific @ 25.09.07, 20:17

esperanto
Если они не целые, то задача NP-полная

Если они целые задача то же класса НП.

esperanto
Это все я понимаю. Но на практике (с программерской точки зрения) эффективными считаются те алгоритмы, которые укладываются в заданные ограничения по времени и по памяти при заданном диапазоне входных параметров. Так что даже экспоненциальные алгоритмы могут быть применимы на практике при небольшом размере входных данных. Автора топика этот алгоритм устроил, значит его можно считать эффективным.

Объясните, пожалуйста, как элементы массива А могут заполняться значениями, если стоит проверка

    if A[j]<>0 then A[j+C[i]]=1;

Изначально все элементы равны 0, кроме нулевого, индекс j до нулевого не доходит, следовательно A[j] всегда будет не равно 0. Как же тогда выполнить A[j+C[i]]=1 ?

asd
Ещё раз код из поста №2 (внимательно смотри вторую строчку):

for i := 1 to 96 do
  for j := sum-C[i] downto 0 do
    if A[j]<>0 then A[j+C[i]]=1;

Понятно...
вот у меня такой простой код для проверки:

        int n = 4;
        int k = 8;
        int[] arC = {6,5,3,2};
        int[] arA = new int[k+1];
        arA[0] = 1;
        for (int i = 1; i < n; i++){
            for (int j = k - arC[i]; j >= 0; j--){
                if (arA[j] != 0)
                    arA[j + arC[i]]= 1;
            }
            
        }
        for (int i = 0; i < k; i++ ){
            System.out.println(arA[i]);
        }

Выдает 1 0 1 1 0 1 0 1
Если индекс в этой последовательности равен возможности получить суммы равную индексу, то ответ получается 0, 2,3,5,7... А 8? 8-это искомая сумма...

Сообщение отредактировано: asd - 15.02.08, 11:33

asd

for (int i = 0; i < k; i++ )

поменяй на

for (int i = 0; i <= k; i++ )

И все станет OK

И ещё:

for (int i = 1; i < n; i++)

поменяй на

for (int i = 0; i < n; i++)

И тогда всё будет совсем правильно.

Сообщение отредактировано: Pacific - 18.02.08, 07:32

to Pacific

Цитата

Если они не целые, то задача NP-полная

К сожалению, если они целые, то задача тоже NP-полная - Гэри, Джонсон "Вычислительная техника и труднорешаемые задачи", задача "Сумма размеров".
Если мы решаем эту задачу динамическим программированиванием, то получаем так называемый "псевдополиномиальный алгоритм" вычислительной сложности O(n*B), где n - количество слагаемых, B - набираемая сумма. Если B очень велико, то динамическое программирование не укладывается в реальное время, и есть два возможных решения. Первый путь - масштабирование алгоритма динамического программирования. Веса всех слагаемых и число B делятся, например, на 100. Алгоритм превращается из точного в приближенный, погрешность можно оценить. Второй путь - придумывание эвристического алгоритма с погрешностью меньшей, чем у масштабированного.

Уважаемые!

У меня та же делема. Как сделать? Смотрю в книгу - вижу фигу.

Можно пример?

Массив из 9 элементов: 1 2 3 4 5 6 7 8 9

Собрать варианты, ну или хотя бы первый возможный, что бы получилась цифра 23. Как то 1+3+4+6+9. И конечно только при использовании элемента массива 1 раз.

Ну дайте хоть один работающий алгоритм ОТ задачи и ДО решения! И желательно на человеческом языке, для обывателей. Вот на таком:

//int n = 4;
КоличествоЭлементовМассиваИсточник = 4;
 
//int k = 8;
КонтрольноеЧисло = 8;
 
//int[] arC = {6,5,3,2};
МассивИсточник = Новый Массив;
МассивИсточник.Добавить(6);
МассивИсточник.Добавить(5);
МассивИсточник.Добавить(3);
МассивИсточник.Добавить(2);
 
//int[] arA = new int[k+1];
МассивРезультат = Новый Массив(КонтрольноеЧисло + 1);
 
//arA[0] = 1;
МассивРезультат[0] = 1;
 
//for (int i = 0; i < n; i++){
Х = 0;
Пока Х < КоличествоЭлементовМассиваИсточник Цикл
    
    //for (int j = k - arC[i]; j >= 0; j--){
    У = КонтрольноеЧисло - МассивИсточник[Х];
    Пока У >= 0 Цикл
        
        //if (arA[j] != 0)
        Если МассивРезультат[У] <> 0 Тогда
 
            //arA[j + arC[i]]= 1;
            МассивРезультат[У + МассивИсточник[Х]] = 1;
 
        КонецЕсли;
        
        У = У - 1;
        
    КонецЦикла;
    
    Х = Х + 1;
    
КонецЦикла;

Перевел, как понял.

Сообщение отредактировано: ghbdtnhjlysv - 27.03.08, 14:30

Набор заданного веса всеми возможными способами с отсечением повторящихся решений.
алгоритм - общая схема алгоритма с возвратом.

Цитата

Алгоритмы с возвратом.
Генерация решения в лексикографическом порядке. Отсечение повторяющихся решений
§1. Задача о весах
УСЛОВИЕ. Имеется разновес, причем гиря определенного веса может быть представлена в нескольких экземплярах.
ВОПРОС. Набрать заданный вес всеми возможными способами с точностью до перестановки гирь.
ПРИМЕР. Разновес: 8, 7, 3, 2, 2, 1, 1, 1.
Набрать вес: 10кг.
Разновес удобно хранить в массиве KRATN[1..N], где N – вес самой тяжелой гири и KRATN[g] – количество экземпляров гири веса g.
Решение (набор веса) будем хранить в массиве SOL[1..N], где SOL[g] – количество экземпляров гири веса g в данном наборе.

Применим обычную схему алгоритма с возвратом.
Пусть V – текущий вес, который нужно набрать. Чтобы набрать этот вес, будем перебирать гири разновеса до тех пор, пока не встретим допустимую.
Условие допустимости:
Гиря g – допустима, если она имеется в разновесе, то есть KRATN[g]>0 и ее вес не превышает набираемого веса V, т.е. g≤V.
Пусть такая g найдена, удалим ее из разновеса, то есть KRATN[g]=KRATN[g]-1 и добавим к решению, то есть SOL[g]=SOL[g]+1. Новый текущий набираемый вес V1=V-g. Затем вызываем рекурсию для уменьшенного веса.
Возврат:
Если допустимой гири в разновесе нет или найдено решение, то последнюю добавленную гирю удаляем из решения и добавляем в разновес.
KRATN[g]=KRATN[g]+1; SOL[g]=SOL[g]-1; V=V1+g – текущий набираемый вес.
Затем возвращаемся на цикл перебора гирь разновеса и вместо гири g берем гирю g-1.

При такой схеме алгоритм будет генерировать повторяющиеся решения. Например, вес 10 будет набран как 2+8 и 8+2. Чтобы избавиться от повторов, будем генерировать решения в антиалфавитном порядке. Это означает следующее.
После того, как к решению была добавлена гиря веса g разрешено брать гири веса меньшего либо равного g. Таким образом, будет сгенерировано только решение 8+2.

Алгоритм {задача о весах}
Данные: разновес, представленный массивом KRATN[1…Ves], Ves – набираемый целый положительный вес.
Результат: печать наборов веса Ves без перестановок гирь.
Переменные: Ves, KRATN, SOL – глобальные.
1 procedure nabor (V, g);
{V - набираемый вес, g - вес последней добавленной к решению гири}
2 begin {nabor}
3 for i = g downto 1 do
4 if (KRATN[i]>0) and (i≤V) then
5 begin
6 KRATN[i] = KRATN[i]-1;
7 SOL[i] = SOL[i]+1;
8 V1 = V-i;
9 if V1=0 then печать SOL
10 else nabor(V1, i);
{возврат}
11 KRATN[i] = KRATN[i]+1;
12 SOL[i] = SOL[i]-1;
13 end;
14 end; {nabor}

1 begin {main}
2 инициализация массива KRATN;
3 for j:=1 to Ves do SOL[J]:= 0;
4 nabor(Ves, Ves);
5 end.

Сообщение отредактировано: Swetlana - 27.03.08, 16:19

Swetlana Ай да УМНИЦА! Ай да СЛАДКАЯ! Целюлю, обнимаю! ОГРОМНОЕ СПАСИБО! Завтра переведу на 1С посмотрим что получится.

Целюлю взаимно . Вообще-то есть работающая программа на Паскале.

Не понимаю!

Какой состав массива KRATN?

"Разновес удобно хранить в массиве KRATN[1..N], где N – вес самой тяжелой гири и KRATN[g] – количество экземпляров гири веса g."

Допустим состав вариантов разновеса: 1, 1, 2, 1. Самый тяжелый разновес 2. Тогда размер массива 2. А где хранится состав разновеса?

У нас 3 гири веса 1 кг, сл-но, KRATN[1]=3 и 1 гиря веса 2 кг, сл-но, KRATN[2]=1.
В массиве хранятся не веса гирь, а количество гирь данного веса. Веса гирь - индексы от минимального веса до максимального.
Пусть у нас разновес 5, 5, 5, 5, 7.
Тогда массив KRATN[5..7] и KRATN[5]=4 (4 гири веса 5 кг), KRATN[6]=0 (гири веса 6кг нет), KRATN[7]=1.

PS Если делать по-хорошему, то кратности (количества) гирь лучше не в массиве хранить, а в динамическом списке. Тогда не придется хранить нули для отсутствующих весов. Но это не обязательно.

"Вот где собака порылась!" "До чего дошел прогресс ..." Т.е. еще нужно выполнить предподготовку данных

А что скажите вот на счет этого алгоритма?

Функция Перебор(list, summ, pos=1)
    
    var resultlist;
    var sublist;
    var subresultlist;
    
    resultlist = СоздатьОбъект("списокзначений");
    
    if summ<=0 then
        return 0;
    endif;
    
    if list.размерсписка()=0 then
        return 0;
    endif;
    
    first = list.получитьзначение(1);
    
    if first = summ then
        resultlist.добавитьзначение(pos);
        return resultlist;
    endif;
    
    if list.размерсписка() = 1 then
        возврат 0;
    endif;
    
    sublist = СоздатьОбъект("списокзначений");
    list.выгрузить(sublist,2);
    
    subresultlist = перебор(sublist, summ-first, pos+1);
    
    if subresultlist<>0 then
        subresultlist.вставитьзначение(1,pos);
        return subresultlist;
    endif;
    
    subresultlist=перебор(sublist,summ,pos+1);
    if subresultlist<>0 then
        return subresultlist;
    endif;
    
    return 0;  
    
КонецФункции
 
Процедура Сформировать()
    
    Массив = СоздатьОбъект("СписокЗначений");
    Массив.ДобавитьЗначение(1);
    Массив.ДобавитьЗначение(2);
    Массив.ДобавитьЗначение(3);
    Массив.ДобавитьЗначение(4);
    Массив.ДобавитьЗначение(5);
    Массив.ДобавитьЗначение(6);
    Массив.ДобавитьЗначение(7);
    Массив.ДобавитьЗначение(8);
    Массив.ДобавитьЗначение(9);
    
    Результат = Перебор(Массив,Контроль);
    
    Если Результат = 0 Тогда
        
        Сообщить("нет вариантов");
        
    Иначе
        
        Результат.ВыбратьЗначение(,,);
        
    КонецЕсли;
 
КонецПроцедуры

Автор конечно не я. Но проверял на некоторых значениях - работает.

Сообщение отредактировано: ghbdtnhjlysv - 28.03.08, 11:43

Забыла сказать. Наборов суммы может быть очень много. Если достаточно одного произвольного набора, то лучше поставить досрочный выход из программы, как только будет найдено первое решение.

А вот интересно как можно быстро выйти из глубоко вложенного цикла?

Давайте по порядку.

Цитата

А вот интересно как можно быстро выйти из глубоко вложенного цикла?

Выход из вложенного цикла или рекурсии осуществляется с помощью логического флага. В программе этот флаг называется STOP. Пока значение флага "ложь", мы вызываем новую рекурсию. Как только найдено 1-е решение, делаем флаг="истина" и выходим на уровень главной программы, откуда был произведен первый рекурсивный вызов.
То же самое с циклами. Заходим в цикл только если флаг="ложь".

Теперь о программе. Она была в Delphi, пришлось пришлось заменить ввод-вывод. Набираемый вес и вес min гири описаны константами, кратности гирь присваиваются прямо внутри программы, набор веса записывается в строку.
Если закомментировать строку STOP:=true; //найдено первое решение , то будут генерироваться все наборы веса.

program www;
 
{$APPTYPE CONSOLE}
 
uses
  SysUtils;
 
const Ves=10;//набираемый вес
      MinV=1;//min вес гири
var
   KRATN,SOL:array[MinV..Ves] of integer;
   k:integer;
   STOP:boolean; //найдено решение
 
procedure nabor(g,v:integer);
var
  i,j,kg:integer;
  s:string;
begin
 if v=0 then
  begin //печать строки с набором суммы
    writeln('Summa:');
    s:='';
    for kg:=Ves downto 1 do
     for j:=1 to SOL[kg] do
      s:=s+'+'+IntToStr(kg);
    writeln(s);
    STOP:=true; //найдено первое решение
   end
  else if (v>0) AND NOT(STOP) then
   begin //добор веса
    for i:=g downto 1 do
     if (v>=i) and (kratn[i]>0) then
      begin
       kratn[i]:=kratn[i]-1;
       sol[i]:=sol[i]+1;
       nabor(i,v-i);
       kratn[i]:=kratn[i]+1;
       sol[i]:=sol[i]-1;
     end;
   end;
end;
 
begin
  for k:=MinV to Ves do
    begin
    KRATN[k]:=0; SOL[k]:=0;
    end;
  KRATN[8]:=1; KRATN[7]:=1; KRATN[3]:=1; KRATN[2]:=2; KRATN[1]:=3;
  STOP:=false; //решение не найдено
  nabor(Ves,Ves);
  readln;
end.

Цитата

А что скажите вот на счет этого алгоритма?

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

Swetlana
А если не удалось набрать сумму?
В SOL что в результате будет?

А если не нашли решения, то как найти решение, максимально близкое, но больше искомого?