knapsack problem

(redirected from 0-1 knapsack problem)

knapsack problem

[′nap‚sak ‚präb·ləm]
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 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.
Proof: It can easily be proven that OVMP is a NP-complete problem by showing that it is a special case of a well-known multi-constraint 0-1 knapsack problem which is already a proven NP-complete problem.
We first show that such a problem is NP complete by proving that it is a special case of a well known multi-constrained 0-1 knapsack problem.
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.