knapsack problem

(redirected from Continuous 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 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).
By removing the upper binding constraint (16), the problem effectively becomes a single constraint continuous knapsack problem for each time period 't'.
T) number of single constraint continuous knapsack problems, each having 'real variables' that are upper bounded.

Full browser ?