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 ?
Computing partitions with applications to the Knapsack Problem.
A Knapsack problem is an assignment problem of combinatorial optimization.
This problem is derived from terminology of Knapsack problem.
We compare the performances among MOEA/D-GO, original MOEA/D, and MOEA/D-PR on six test instances of the multiobjective 0/1 knapsack problem.
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.
However, the algorithm for the knapsack problem [2] has not been known yet.
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.
This integer programming model is an application of a classic mathematical form known as the 1,0 knapsack problem (Wagner 1975).
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.