#11003 - Boxes

Solved By:	wesley
Theory Difficulty:	easy
Coding Difficulty:	trivial
Algorithms Used:	dynamic programming
Solution Description:	We have to use the boxes in the order they're given, from bottom to top. Let a[i] be the most capacity that we have remaining on a stack of height i. Initially, a[0] = infinity, and a[i] = -1 for i != 0. Let Wi and Ci be the weight and capacity of the ith box. We get: a[j+1] = max(a[j+1], min(a[j]-Wi, Ci)) for all j <= i. a[j]-Wi is how much capacity would remain if we put box i on top of the stack of height j. But, if Ci is smaller, then that becomes the new limit. And then, we take the maximum of using this box, or not using it. Process the different j's in descending order, or you'll get an error where you try to use the same box multiple times.