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)
“Play is a major avenue for learning to manage anxiety. It gives the child a safe space where she can experiment at will, suspending the rules and constraints of physical and social reality. In play, the child becomes master rather than subject.... Play allows the child to transcend passivity and to become the active doer of what happens around her.”
—Alicia F. Lieberman (20th century)