Translation

powered by

Computing (FOLDOC) dictionary

knapsack problem

application, mathematics 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

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