Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Вывод 1 Вывод 2 Вывод 3. Нельзя перебрать все подмножества, их всего 2500




Ввод 1 Ввод 2 Ввод 3

3 3 5

1 1 2 1 3 2 49 100 98 49 0

5 7 10

Нельзя перебрать все подмножества, их всего 2500. Максимальное значение суммы 50000. Найдем все возможные значения сумм. Заполним массив B[0..500,50000] логических значений. Положим B[L, S] = true, если можно подобрать коэффициенты k1, k2,..., kL со значениями 0 и 1 так, что k1A1+ k 2A2 +...+kLAL= S.

При L=0 слагаемых нет, поэтому B[0,0]=true, B[0,S]=false при S от 1 до 50000. Найдем B[L,S] при L>0.

В сумму S слагаемое AL может входить или не входить. Если слагаемое AL входит, то k1A1+ k 2A2 +...+kL-1AL-1= S - AL, если не входит, то k1A1+ k 2A2 +...+kL-1AL-1= S. Значит, сумму S с помощью L слагаемых можно получить одним из двух вариантов:

· получить S с помощью L-1 слагаемого;

· получить S-AL с помощью L-1 слагаемого.

Отсюда B[L,S]=B[L-1,S] or B[L-1,S-A[L]].

На самом деле двумерный массив B не нужен, достаточно двух массивов по 50000 логических элементов для двух соседних шагов. Более того, можно обойтись одним массивом B[0..50000], заполняя его в обратном порядке.

 

Program Sums;

Var

N: integer;

A: array [1..100] of integer;

B: array [0..50000] of boolean; {достижимость сумм}

Fin,Fout: text;

i,k: integer;

Sum,S: integer;

Begin

Assign(Fin,'input.txt’);

Reset(Fin);

ReadLn(Fin,N);

Sum:=0; {общая сумма элементов множества}

For i:=1 to N do

begin

Read(Fin,A[i]);

Sum:=Sum+A[i]

end;

Close(Fin);

B[0]:=true;

For S:=1 to Sum do B[S]:=false; {инициализация}

For i:=1 to N do

For S:=Sum downto A[i] do

B[S]:=B[S] or B[S-A[i]];

k:=0; {счетчик}

For S:=0 to Sum do

if B[S] then k:=k+1; {новое значение суммы}

Assign(Fout,'output.txt');

Rewrite(Fout);

WriteLn(Fout,k);

Close(Fout);

End.

Сформулируем общий принцип, лежащий в основе решения задач динамического программирования, называемый принципом оптимальности. Каково бы ни было состояние процесса перед очередным шагом, надо выбирать управление на этом шаге так, чтобы стоимость на данном шаге плюс оптимальная стоимость на всех последующих шагах была минимальной.

Отметим в заключение некоторые дополнительные аспекты применения методов динамического программирования.

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

6. Функция стоимости может выражаться не суммой, а произведением стоимостей на отдельных шагах.

7. Процесс может рассматриваться в первую очередь и от начала к концу, но описанный порядок более легок для понимания.

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

 




Поделиться с друзьями:


Дата добавления: 2014-01-11; Просмотров: 340; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.008 сек.