исследование операций задача о ранце [о рюкзаке] (задача о наилучшем выборе предметов из общего их количества таким образом, чтобы их суммарный вес либо габариты либо иной подобный параметр не превышал заданного, а их суммарная полезность была максимальной) Синоним(ы): problem of knapsack
математика задача о ранце
Given a set of items, each with a cost and a value, determine the number of each item to include in a collection so that the total cost is less than some given cost and the total value is as large as possible. The 0/1 knapsack problem restricts the number of each items to zero or one. Such constraint satisfaction problems are often solved using dynamic programming. The general knapsack problem is NP-hard, and this has led to attempts to use it as the basis for public-key encryption systems. Several such attempts failed because the knapsack problems they produced were in fact solvable by polynomial-time algorithms. .