https://discopal.ispras.ru/index.php?action=history&feed=atom&title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D1%80%D1%8E%D0%BA%D0%B7%D0%B0%D0%BA%D0%B5Задача о рюкзаке - История изменений2026-05-02T12:53:03ZИстория изменений этой страницы в викиMediaWiki 1.26.4https://discopal.ispras.ru/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D1%80%D1%8E%D0%BA%D0%B7%D0%B0%D0%BA%D0%B5&diff=1116&oldid=prevWikiSysop: 1 версия2008-10-23T16:48:02Z<p>1 версия</p>
<p><b>Новая страница</b></p><div>Задача о рюкзаке ([[Knapsack problem]]) содержательно <br />
означает выбор предметов с наибольшей суммарной<br />
стоимостью, умещающихся в рюкзак заданного размера.<br />
Эта задача часто возникает при выборе оптимального управления<br />
в различных экономико-финансовых областях (распределение<br />
бюджета отдела по проектам и т. п.).<br />
<br />
Задача имеет несколько более формальных постановок, представленных ниже.<br />
<br />
== 0-1 Рюкзак ==<br />
<br />
Даны натуральные числа <m>a_1,\ldots,a_n</m> <br />
(называемые «размерами» или «весами» предметов), <br />
<m>c_1, \ldots, c_n</m> («стоимости» предметов) <br />
и ''B'' («размер» рюкзака).<br />
<br />
Найти максимальное значение <m>f^*</m> целевой функции<br />
<m> f \equiv \sum_{i=1}^n c_i x_i \to \max </m><br />
<br />
с ограничением на размер «рюкзака»<br />
<m> \sum_{i=1}^n a_i x_i \leq B, \ \ \ x_i \in \{0,1\}.</m><br />
<br />
<br />
==Алгоритмы==<br />
* [[Задача о рюкзаке:жадный алгоритм]]<br />
* [[Задача о рюкзаке:динамическое программирование]]<br />
* [[Задача о рюкзаке:PTAS]]<br />
<br />
[[Category:Задачи]]<br />
{{replicate-from-custiswiki-to-lib}}</div>WikiSysop