Изменения

Перейти к: навигация, поиск

Задача о рюкзаке

2300 байт добавлено, 08:33, 1 сентября 2022
Нет описания правки
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
|+
|-align="center"
|'''НЕТ ВОЙНЕ'''
|-style="font-size: 16px;"
|
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 
''Антивоенный комитет России''
|-style="font-size: 16px;"
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
|-style="font-size: 16px;"
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
|}
 
{{Задача
|definition =
'''Задача о рюкзаке '''(''англ. Knapsack problem'') — дано дано <tex>N</tex> предметов, <tex>n_i</tex> предмет имеет массу массу <tex> w_i w_i > 0</tex> и стоимость стоимость <tex> p_i p_i > 0</tex>. Необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины величины <tex>W</tex> (вместимость рюкзака), а суммарная стоимость была максимальна.
}}
== Формулировка задачи ==
Дано Дано <tex>N</tex> предметовпредметов, <tex>W</tex> — вместимость рюкзака, <tex>w=\{w_{1},w_{2},\dots,w_{N}\}</tex> — соответствующий ему набор положительных целых весов, <tex>p=\{p_{1},p_{2},\dots,p_{N}\}</tex> — соответствующий ему набор положительных целых стоимостей. Нужно найти набор бинарных величин величин <tex>B=\{b_{1},b_{2},\dots,b_{N}\}</tex>, где <tex>b_{i} = 1 </tex>, если предмет <tex>n_i</tex> включен в набор, <tex> b_{i} = 0 </tex>, если предмет <tex>n_i</tex> не включен, и такой что:
#<tex>b_{1} w_{1}+ \dots + b_{N} w_{N} \leqslant W</tex>
== Метод динамического программирования ==
Пусть Пусть <tex>A(k, ss)</tex> есть максимальная стоимость предметов, которые можно уложить в рюкзак вместимости вместимости <tex>s</tex>, если можно использовать только первые первые <tex>k</tex> предметовпредметов, то есть <tex>\{n_1,n_2,\dots,n_k\}</tex>, назовем этот набор допустимых предметов для <tex>A(k,s)</tex>.
<tex>A(k, 0) = 0</tex>
Анонимный участник

Навигация