# knapsack problem

Also found in: Wikipedia.

## knapsack problem

[′nap‚sak ‚präb·ləm] (mathematics)

The problem, given a set of integers {

*A*_{1},*A*_{2}, …,*A*_{n }} and a target integer*B*, of determining whether a subset of the*A*_{i }can be selected without repetition so that their sum is the target*B*.## 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 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.

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.

Want to thank TFD for its existence? Tell a friend about us, add a link to this page, or visit the webmaster's page for free fun content.

Link to this page: