knapsack 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 ?
The problems that will be introduced in this paper are: traveling salesman problem (TSP), 0/1 Knapsack problem, Shubert function, and system of linear equations.
Keywords: evaluation, genetic, mutation operator, TSP, 0/1 knapsack problem, Shubert function, linear system
n] - 1 times is necessary in the classical calculation in the knapsack problem.
As for n pieces of different weight luggage, the knapsack problem requests the best combination of the luggage packed into the knapsack that a weight k is assumed to be an upper bound [2].
Computing Partitions with Applications to the Knapsack Problem.
Another method, based on a mathematical puzzle known as the knapsack problem, initially looked promising, but researchers discovered serious loopholes in many of the different types of knapsack cryptosystems that had been constructed (SN: 11/24/84, p.
The authors characterize the tax planning problem as a 0-1 knapsack problem and employ PROC LP to optimize the overall tax burden.
In closing, the authors would like to point out this 0-1 knapsack problem can be solved by Dynamic Programming(4) or by the Slippery Algorithm.
By solving the knapsack problem for various values of T, many different alternative combinations of total habitat value protected and total timber set aside can be generated.
The decomposed problem actually becomes a single constraint continuous knapsack problem, which is known to be one of the easier NP-hard problems, solvable in quasi-polynomial times (Pisinger, 2005).
This problem is, in fact, the optimization version of SUBSET Sum, which is a special case of the general KNAPSACK problem.
We should mention that the security of the Knapsack Cryptosystem is based on the fact that the super increasing knapsack problem (Merkle & Helman, 1978) is an NP-complete problem.