Multiple Constraints
If there is more than one constraint (for example, both a volume limit and a weight limit, where the volume and weight of each item are not related), we get the multiply constrained knapsack problem, multidimensional knapsack problem, or m-dimensional knapsack problem. (Note, "dimension" here does not refer to the shape of any items.) This has 0-1, bounded, and unbounded variants; the unbounded one is shown below.
| maximize | ||
| subject to | for all | |
| , integer | for all | |
The 0-1 variant (for any fixed ) was shown to be NP-complete around 1980 and more strongly, has no FPTAS unless P=NP.
The bounded and unbounded variants (for any fixed ) also exhibit the same hardness.
For any fixed, these problems do admit a pseudo-polynomial time algorithm (similar to the one for basic knapsack) and a PTAS.
Read more about this topic: List Of Knapsack Problems
Famous quotes containing the words multiple and/or constraints:
“Combining paid employment with marriage and motherhood creates safeguards for emotional well-being. Nothing is certain in life, but generally the chances of happiness are greater if one has multiple areas of interest and involvement. To juggle is to diminish the risk of depression, anxiety, and unhappiness.”
—Faye J. Crosby (20th century)
“The analogy between the mind and a computer fails for many reasons. The brain is constructed by principles that assure diversity and degeneracy. Unlike a computer, it has no replicative memory. It is historical and value driven. It forms categories by internal criteria and by constraints acting at many scales, not by means of a syntactically constructed program. The world with which the brain interacts is not unequivocally made up of classical categories.”
—Gerald M. Edelman (b. 1928)