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:
“There is a continual exchange of ideas between all minds of a generation. Journalists, popular novelists, illustrators, and cartoonists adapt the truths discovered by the powerful intellects for the multitude. It is like a spiritual flood, like a gush that pours into multiple cascades until it forms the great moving sheet of water that stands for the mentality of a period.”
—Auguste Rodin (1849–1917)
“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)