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

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 что в результате будет?

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