knapsack problem


knapsack problem

[′nap‚sak ‚präb·ləm] (mathematics) The problem, given a set of integers {A1, A2, …, An } and a target integer B, of determining whether a subset of the Ai can be selected without repetition so that their sum is the target B.

knapsack problem

(application, mathematics)Given a set of items, each with acost and a value, determine the number of each item to includein a collection so that the total cost is less than some givencost and the total value is as large as possible.

The 0/1 knapsack problem restricts the number of each items tozero or one.

Such constraint satisfaction problems are often solved usingdynamic programming.

The general knapsack problem is NP-hard, and this has led toattempts to use it as the basis for public-key encryptionsystems. Several such attempts failed because the knapsackproblems they produced were in fact solvable bypolynomial-time algorithms.