Форум по Delphi программированию

Delphi Sources



Вернуться   Форум по Delphi программированию > Все о Delphi > Разное
Ник
Пароль
Регистрация <<         Правила форума         >> FAQ Пользователи Календарь Поиск Сообщения за сегодня Все разделы прочитаны

Ответ
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 15.12.2005, 23:20
jishimuro jishimuro вне форума
Прохожий
 
Регистрация: 15.12.2005
Сообщения: 1
Репутация: 10
Восклицание Помогите с решением задачи (динамическое программирование)

Формулировка задачи.
Дано мн-во целых неотрицательных чисел (проще говоря какой-то массив размера 'n' из натуральных чисел) и натуральное число 'm'. Необходимо найти все подмн-ва данного мн-ва, сумма элементов которых будет равна данному числу 'm' (т.е. найти все разложения данного числа по элементам данного массива).

Например:
Пусть дан массив A={1,3,2,9,6} (n=5) и пусть m=6. Очевидно, что искомыми мн-ми являются:
А1={1,3,2} и
A2={6}
(1+2+3=6, 6=6)

Вот такая задача. Надеюсь всё подробно и понятно. Сразу хочу выразить огромную благодарность всем, кто откликнется. Если кто-то решит предоставить код программы, то желательно на Delphi.
Ответить с цитированием
  #2  
Старый 14.01.2006, 15:51
Necrom@ncer Necrom@ncer вне форума
Прохожий
 
Регистрация: 14.01.2006
Сообщения: 1
Репутация: 10
По умолчанию Помощь

попробуй следующий алгоритм:

procedure Find(mas:array of word;m:word);
var
imas,nmas:array of Word;
k,j:word;
i:longint;
max,min:word;
h,s:real;
isk:array of word;
begin
max:=0;
min:=0;
k:=0;
{я попытался максимально
проанализировать алгоритм для массивов с огромным количеством элементов ,получился алгоритм в котором я не до конца уверен }
//Начнем
for i:=0 to High(mas) do //найдем максимум и минимум
begin
if mas[i]>max then
max:=mas[i]
else
if mas[i]<min then
min:=mas[i];
end;
setlength(imas,max-min); //сейсчас поюзаем метод
for i:=0 to max-min do //быстрой сортировки
begin //ее суть подсчитать количество
inc(imas[mas[k]]); //повторяющихся символов в
inc(k); //массиве
end;
j:=0;
for i:=0 to high(imas) do //сортируем
begin
for k:=1 to imas[i] do
begin
mas[i+j]:=i+1;
inc(j);
end;
end;
for i:=0 to high(mas) do
nmas[i]:=mas[i];//приходиться копировать массив
for i:=high(nmas) downto 0 do //удаляем лишнее
if nmas[i]<m then begin
setlength(nmas,i);
break;
end;
{все предидущее для того чтобы удалить лишнее из массива и оптимизировать поиск.
Далее я использую характеристики множеств,то бишь среднее арифметическое значение и количество элементов;если среднее арифметическое значение это
h и i-количество элементов, то они связаны уравнением
m=h*i ,где m-это сумма элементов ,теперь мы просто генерим элементы искомых множеств}
for i:=1 to high(nmas) do begin
h:=m/i;
setlength(isk,i);
while s<>h do begin
s:=0;
k:=0;
while k<>i-1 do begin
Randomize;
isk[k]:=min+random(max-min+1);
if imas[isk[k]]=0 then //проверка на существование
continue; // быстрее чем обычным способом
inc(k);
end;
for k:=0 to i-1 do
s:=s+isk[k]/i;
end;
for j:=0 to high(isk) do
Form1.RichEdit1.Lines.Add(Inttostr(Isk[j]));//здесь по желанию
end;
end;
Вот и все!Удачи!

Последний раз редактировалось Necrom@ncer, 14.01.2006 в 20:16.
Ответить с цитированием
Ответ


Delphi Sources

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB-коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Быстрый переход


Часовой пояс GMT +3, время: 21:27.


 

Сайт

Форум

FAQ

RSS лента

Прочее

 

Copyright © Форум "Delphi Sources" by BrokenByte Software, 2004-2023

ВКонтакте   Facebook   Twitter