knapsack problem

(redirected from 0-1 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 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 ?
At this point, the CC and RB joint distribution problem [P.sub.11] is mapped to a multidimensional 0-1 knapsack problem.
Toth, "Dynamic programming and strong bounds for the 0-1 Knapsack Problem," Management Science, vol.
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 0-1 knapsack problem and multidimensional knapsack problem are the most common and important in the family of knapsack problems and have been extensively studied [1].
Guo, "Binary differential evolution algorithm for 0-1 knapsack problem," Computer Engineering and Design, vol.
We set parameter [p.sub.m] = 2/D for the 0-1 knapsack problem and [p.sub.m] [member of] [0.005,0.1] for continuous optimal problem.
Figures 19, 20, 21, 22, 23, 24, 25, and 26 show relative convergence rate of the QEAs for 0-1 knapsack problem with multiple strongly correlated data instances.
The message management is modeled as a 0-1 knapsack problem when node's buffer overflows.
The authors characterize the tax planning problem as a 0-1 knapsack problem and employ PROC LP to optimize the overall tax burden.
In addition, despite successful application to the solution of 0-1 knapsack problem by many methods, in fact, it is still a very active research area, because many existing algorithms do not cope well with some new and more intractable 0-1 knapsack problems hidden in the real world.
The optimal solution to OVMP is deceptively difficult to formulate as the problem comes under a class of very hard problems called Multi-Constraint 0-1 Knapsack problem [5] which has been dealt extensively in mathematics with its applications in computer science, economics, genetics and other disciplines.
As is mentioned above, metaheuristic methods have been proven to be an effective means to cope with the combinatorial optimization problems including 0-1 knapsack problem. Unlike deterministic search approaches which have the drawbacks of being trapped into local minima unavoidably, the main advantage of metaheuristic methods can deliver satisfactory solutions in a reasonable time.