Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[13.58.247.231] |
|
Страницы: (2) 1 [2] все ( Перейти к последнему сообщению ) |
Сообщ.
#16
,
|
|
|
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++) И тогда всё будет совсем правильно. |
Сообщ.
#17
,
|
|
|
to Pacific
Цитата Если они не целые, то задача NP-полная К сожалению, если они целые, то задача тоже NP-полная - Гэри, Джонсон "Вычислительная техника и труднорешаемые задачи", задача "Сумма размеров". Если мы решаем эту задачу динамическим программированиванием, то получаем так называемый "псевдополиномиальный алгоритм" вычислительной сложности O(n*B), где n - количество слагаемых, B - набираемая сумма. Если B очень велико, то динамическое программирование не укладывается в реальное время, и есть два возможных решения. Первый путь - масштабирование алгоритма динамического программирования. Веса всех слагаемых и число B делятся, например, на 100. Алгоритм превращается из точного в приближенный, погрешность можно оценить. Второй путь - придумывание эвристического алгоритма с погрешностью меньшей, чем у масштабированного. |
Сообщ.
#18
,
|
|
|
Уважаемые!
У меня та же делема. Как сделать? Смотрю в книгу - вижу фигу. Можно пример? Массив из 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; КонецЦикла; Перевел, как понял. |
Сообщ.
#19
,
|
|
|
Набор заданного веса всеми возможными способами с отсечением повторящихся решений.
алгоритм - общая схема алгоритма с возвратом. Цитата Алгоритмы с возвратом. Генерация решения в лексикографическом порядке. Отсечение повторяющихся решений §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. |
Сообщ.
#20
,
|
|
|
Swetlana Ай да УМНИЦА! Ай да СЛАДКАЯ! Целюлю, обнимаю! ОГРОМНОЕ СПАСИБО! Завтра переведу на 1С посмотрим что получится.
|
Сообщ.
#21
,
|
|
|
Целюлю взаимно . Вообще-то есть работающая программа на Паскале.
|
Сообщ.
#22
,
|
|
|
Не понимаю!
Какой состав массива KRATN? "Разновес удобно хранить в массиве KRATN[1..N], где N – вес самой тяжелой гири и KRATN[g] – количество экземпляров гири веса g." Допустим состав вариантов разновеса: 1, 1, 2, 1. Самый тяжелый разновес 2. Тогда размер массива 2. А где хранится состав разновеса? |
Сообщ.
#23
,
|
|
|
У нас 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 Если делать по-хорошему, то кратности (количества) гирь лучше не в массиве хранить, а в динамическом списке. Тогда не придется хранить нули для отсутствующих весов. Но это не обязательно. |
Сообщ.
#24
,
|
|
|
"Вот где собака порылась!" "До чего дошел прогресс ..." Т.е. еще нужно выполнить предподготовку данных
А что скажите вот на счет этого алгоритма? Функция Перебор(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 Тогда Сообщить("нет вариантов"); Иначе Результат.ВыбратьЗначение(,,); КонецЕсли; КонецПроцедуры Автор конечно не я. Но проверял на некоторых значениях - работает. |
Сообщ.
#25
,
|
|
|
Забыла сказать. Наборов суммы может быть очень много. Если достаточно одного произвольного набора, то лучше поставить досрочный выход из программы, как только будет найдено первое решение.
|
Сообщ.
#26
,
|
|
|
А вот интересно как можно быстро выйти из глубоко вложенного цикла?
|
Сообщ.
#27
,
|
|
|
Давайте по порядку.
Цитата А вот интересно как можно быстро выйти из глубоко вложенного цикла? Выход из вложенного цикла или рекурсии осуществляется с помощью логического флага. В программе этот флаг называется 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. Цитата А что скажите вот на счет этого алгоритма? Если среди элементов массива будут одинаковые слагаемые, то алгоритм будет выдавать повторяющиеся решения в случае, если мы хотим получить все наборы суммы. А если нам нужно ровно одно решение, то все в порядке. |
Сообщ.
#28
,
|
|
|
Swetlana
А если не удалось набрать сумму? В SOL что в результате будет? |
Сообщ.
#29
,
|
|
|
А если не нашли решения, то как найти решение, максимально близкое, но больше искомого?
|