|
|
| Строка 1: |
Строка 1: |
| − | Задача о рюкзаке ([[Knapsack problem]]) содержательно
| + | #REDIRECT [[discopal:{{PAGENAME}}]] |
| − | означает выбор предметов с наибольшей суммарной
| + | |
| − | стоимостью, умещающихся в рюкзак заданного размера.
| + | |
| − | Эта задача часто возникает при выборе оптимального управления
| + | |
| − | в различных экономико-финансовых областях (распределение
| + | |
| − | бюджета отдела по проектам и т. п.).
| + | |
| − | | + | |
| − | Задача имеет несколько более формальных постановок, представленных ниже.
| + | |
| − | | + | |
| − | == 0-1 Рюкзак ==
| + | |
| − | | + | |
| − | Даны натуральные числа <m>a_1,\ldots,a_n</m>
| + | |
| − | (называемые «размерами» или «весами» предметов),
| + | |
| − | <m>c_1, \ldots, c_n</m> («стоимости» предметов)
| + | |
| − | и ''B'' («размер» рюкзака).
| + | |
| − | | + | |
| − | Найти максимальное значение <m>f^*</m> целевой функции
| + | |
| − | <m> f \equiv \sum_{i=1}^n c_i x_i \to \max </m>
| + | |
| − | | + | |
| − | с ограничением на размер «рюкзака»
| + | |
| − | <m> \sum_{i=1}^n a_i x_i \leq B, \ \ \ x_i \in \{0,1\}.</m>
| + | |
| − | | + | |
| − | | + | |
| − | ==Алгоритмы==
| + | |
| − | * [[Задача о рюкзаке:жадный алгоритм]]
| + | |
| − | * [[Задача о рюкзаке:динамическое программирование]]
| + | |
| − | * [[Задача о рюкзаке:PTAS]]
| + | |
| − | | + | |
| − | [[Category:Задачи]]
| + | |
| − | {{replicate-from-custiswiki-to-lib}}
| + | |
