This is the problem description:

The Amazing Circus has K acrobats that perform great human towers by jumping on the shoulders of each other. The Circus director wants to creating the tallest tower possible to enter the Guinness record and attract more costumers.

Each acrobat i has weight W[i] and strength S[i]. An acrobat can carry on its back a stack of acrobats whose total weight is within S[i]. This should include W[i], its own weight, so assume that S[i]≥W[i] always.

Return the height of the tallest human tower that the Amazing Circus can build.

Constraints:

3 <= K <= 5000

1 <= weight <= capacity <= 10^6.

So for this problem, at first I think this one is somewhat similar to other greedy algorithm problem. But when I looked at the constraints, it seems that the constraints is relatively large so brute forcing or exhaustive search wouldn't work well. Any ideas on how can I approach to solve this problem?

CodePudding user response：

Here's a solution with O(n^2) search space (n = K, the total number of acrobats). Let f(i, h) represent the weight of the lightest tower of height h up to the ith acrobat, where the acrobats have been ordered by strength ascending. Then:

f(i, h) = min(
  f(i - 1, h),
  weight(i)   f(i - 1, h - 1)
     if strength(i) ≥ weight(i)   f(i - 1, h - 1) else Infinity
)

To explain the ordering trick, as adapted from COMP3121/9101/3821/9801 Lecture Notes; More on Dynamic Programming (DP); LiC: Aleks Ignjatovic; School of Computer Science and Engineering; The University of New South Wales; Sydney, Australia:

We'd like to prove that we can rearrange any legitimate tower to be ordered by strength ascending. To do this we need to show that any consecutive pair where

(1) strength(a_i 1) < strength(a_i)

can be legitimately swapped, since then we could apply bubble sort. In other words, that

(2) (Sum j=1...i-1 of weight(a_j))   weight(a_i 1)   weight(a_i) ≤ strength(a_i)

The original, legitimate tower has

(3) (Sum j=1...i−1 of weight(a_j))   weight(a_i)   weight(a_i 1) ≤ strength(a_i 1)

Substitute (1) in the right side and switch the last two terms on the left:

(Sum j=1...i−1 of weight(a_j))   weight(a_i 1)   weight(a_i) ≤ strength(a_i)