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 ?
Knapsack problem is defined as a problem in combinatorial optimization that makes use of dynamic programming (DP) in computing its solution (Ahmad et al., 2016).
(1) 0-1 multidimensional knapsack problem (0-1MKP): 0-1MKP comprises m items and n knapsacks with different capacities [Ca.sub.i], where i [member of] {1,2, ...,n} and n is the number of knapsacks.
We note that if [DELTA][c.sub.ik], [DELTA][[eta].sub.ik] are constant for all k, then this problem is equivalent to the unbounded knapsack problem, which is NP-hard; see, e.g., [30].
As discussed in Section 3, the task of searching for feasible assignment scheme can be converted to a series of one-dimensional 0/1 knapsack problem, which can be exactly solved by dynamic programming algorithms [31-36].
Currently, the antenna selection problem in MIMO radar system is usually modeled as a knapsack problem (KP).
So as to optimize these problems, such as unit commitment [1], feature selection [2, 3], task scheduling [4, 5], and 0-1 knapsack problem [6, 7], binary algorithms are proposed to generate binary solutions.
The knapsack problem is one of typical NP-hard combinatorial optimization problems in operation research, which includes a variety of knapsack problems such as the 0-1 knapsack problems and multidimensional knapsack problems.
There is a set of classic problems that can be treated in binary form, such as the well-known knapsack problem [53], the set covering problem [54], and the traveling salesman problem [55].
It can be described as multiple knapsack problem. It's difficult to build the model and the solving procedure is complex.
Computing partitions with applications to the Knapsack Problem. Journal of the ACM, 1974, v.
This problem is derived from terminology of Knapsack problem. It is to optimize when a set of object with different characteristic (volume, weight and other measurement) packed into to numbers of bins, GA helps to minimize the number of bins used.