Direct Generalizations
One common variant is that each item can be chosen multiple times. The bounded knapsack problem specifies, for each item j, an upper bound uj (which may be a positive integer, or infinity) on the number of times item j can be selected:
maximize | ||
subject to | ||
integral for all j |
The unbounded knapsack problem (sometimes called the integer knapsack problem) does not put any upper bounds on the number of times an item may be selected:
maximize | ||
subject to | ||
integral for all j |
The unbounded variant was shown to be NP-complete in 1975 by Lueker. Both the bounded and unbounded variants admit an FPTAS (essentially the same as the one used in the 0-1 knapsack problem).
If the items are subdivided into k classes denoted, and exactly one item must be taken from each class, we get the multiple-choice knapsack problem:
maximize | ||
subject to | ||
for all | ||
for all and all |
If for each item the profits and weights are identical, we get the subset sum problem (often the corresponding decision problem is given instead):
maximize | ||
subject to | ||
If we have n items and m knapsacks with capacities, we get the multiple knapsack problem:
maximize | ||
subject to | for all | |
for all | ||
for all and all |
As a special case of the multiple knapsack problem, when the profits are equal to weights and all bins have the same capacity, we can have multiple subset sum problem:
Quadratic knapsack problem:
maximize | |||
subject to | |||
for all |
Set-Union Knapsack Problem:
SUKP is defined by Kellerer et al (on page 423) as follows:
Given a set of items and a set of so-called elements, each item corresponds to a subset of the element set . The items have non-negative profits, and the elements have non-negative weights, . The total weight of a set of items is given by the total weight of the elements of the union of the corresponding element sets. The objective is to find a subset of the items with total weight not exceeding the knapsack capacity and maximal profit.
Read more about this topic: List Of Knapsack Problems
Famous quotes containing the word direct:
“I, who travel most often for my pleasure, do not direct myself so badly. If it looks ugly on the right, I take the left; if I find myself unfit to ride my horse, I stop.... Have I left something unseen behind me? I go back; it is still on my road. I trace no fixed line, either straight or crooked.”
—Michel de Montaigne (15331592)