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:
“Creativity seems to emerge from multiple experiences, coupled with a well-supported development of personal resources, including a sense of freedom to venture beyond the known.”
—Loris Malaguzzi (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)