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)
“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)