knapsack problem

(redirected from Backpack problem)
Also found in: Wikipedia.

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 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.

References in periodicals archive ?
Doctors say parents don't need to worry that the backpack problem will cause scoliosis or serious injury.
The backpack problem is made worse by the fact that so many of today's children are obese.
The American Chiropractic Association has offered the following tips to help prevent backpack problems in school children: