UVa 11003

From Algorithmist
Jump to navigation Jump to search

11003 - Boxes[edit]

Summary[edit]

Given the relatively small scale (the maximum load of each box is no bigger than 3000) of the problem, it can be solved using dynamic programming within the time limit.

Explanation[edit]

Let a two-dimensional array element DP[i][j] be the max. number of boxes whose ID ranges from 1 to i that can be stacked on the surface whose load capacity is j. Let the range of i and j be [1,I] and [0,J] respectively. We use weight[i] to denote the weight of box i and capacity[i] the load capacity of box i. Then DP[i][j] can be computed as following.

Initialization: DP[N][j] = 1 for j=weight[N]..J .

Loop: DP[i][j] is the maximum of the following two values:

  • DP[i+1][j], when box i is not used in the stacking;
  • 1 + DP[i+1][min{capacity[i], j-weight[i]}], when box i is stacked below.

Note that the surface (the ground) that support the box at the bottom can hold any weight and any box could be the one that is at the bottom of the stack. So, these cases has to be handled separately. If box i is at the bottom, then the height of the current stack is 1 + DP[i+1][capacity[i]]. The maximum of these values is the solution to this problem.

Input[edit]

2
1 1
1 1
2
3000 3000
3000 3000
2
1501 1501
1501 1501
3 
1 1
3000 3000
3000 3000
5 
2 10 
2 10 
2 21 
20 1 
1 2
7
10 10
100 200
5 5 
100 100
5 5
50 50
50 50
0

Output[edit]

2
2
2
2
4
4