The best strategy that the fireman should use in this problem is?

Question

Problem:
Suppose there is a building with $10$ floors. Each floor has only one room and each room has exactly one person in it. On the first floor there is a child in the room who weighs $10$kg, on the second floor there is a child in the room who weighs $20$kg, on the third floor there is a child in the room who weighs $30$kg . . . on the tenth floor there is a child in the room who weighs $100$kg. Adjacent to the bottom of the building there is a deep swimming pool so that if someone were to jump from the top they would land in the water and survive. Each floor is separated by a distance of $10$ metres (ground floor and first floor as well). Each room also has a window. Unfortunately, a huge fire breaks out in the building due to which huge amount of smoke are released. As a result, all the children suffocate and fall unconscious. They need to be saved! Fortunately, there is a very strong, fast and talented fireman outside the building. He knows of all the details mentioned above. He puts a huge ladder that aligns with all the windows of all rooms. He climbs the ladder at a speed of $10m$/s(when he is carrying no extra weight). When he is carrying extra weight $W$, his climbing speed becomes $10-\frac{W}{10}$. So when he is carrying $10$kg with him, his speed becomes $9$m/s, when carrying $20$kg it is $8$m/s and so on. When he is carrying $100$kg it becomes zero. Whenever the fireman arrives in a child's room, he puts him/her on his back and jumps with them into the pool, swims and leaves them safe at the edge of the pool outside the water, then gets right back to saving other children. He can carry multiple children at once(his climbing speed will decrease accordingly). He can also jump down with multiple children at once.

Example - He can climb upto the first floor room(taking 1s), put the child on his back, then instead of jumping down he can climb with the 10kg child on his back to the second floor room(which will take $\frac{10}{9}$s). Now he can jump down with both of them at once. Assume that jumping down and swimming them to safety takes no time.

The problem is-What is the best strategy, i.e., how can he save everyone the fastest. He cannot lift more than $100$kg at once.


My best answer is $≈50.44$s.
I tried three different strategies. First, one by one, which took $55$s. Second, I tried-take the first four together and jump from first floor, then one by one from the fifth floor onwards, which takes $≈51.04$s. I am not going to tell you how I got $50.44$s, figure it out yourselves. I was able to find times worse than $55$s, but not better than $50.44$s. Can you find any better strategies? And is there any pattern to generalize a variation of the problem? Like one in which where there are $20$ floors and kids weigh up to $200$kg. Also please tell me if there already exists such a problem.

Answer 1

Visualize a directed graph with 10 nodes with edges from node $1$-$2$, $2$-$3$ & a dummy node (the ground) connected with every node.
Weight/cost of edges $E_{u,v}$ is time, $t=$ distance $D_v$ $/$ speed ${100-(\sum_{u=1}^v w_u)} \over 10$ where $W$ is both index of node & number of kids carried.

Edges from each node to dummy have cost of $0$ while the input cost $D_v/10$ for each node $v$

Using dynamic programming with floors as stages and options of either a carrying a kid from there & climbing further a state or jumping as another state:
Boundary condition: minimum time at top most node
$f_{10} = 0 $
$f_9 = \min ({D_{10} /10 + f_{10}, \frac {D_{9,10}}{100-(\sum_{u=8}^9 w_u)} } + f_{10},..., \frac {D_{9,10}}{100-(\sum_{u=1}^9 w_u)} + f_{10} )$

For node $v$
$ f_v =\min (D_{v+1}/10+f_{v+1}, \frac {D_{v,v+1}}{100-(\sum_{u=v-1}^v w_u)} + f_{v+1}..., \frac {D_{v,v+1}}{100-(\sum_{u=1}^v w_u)} + f_{v+1})$

Basically at every node $1-9$ need to enumerate option of either jumping down & then getting back to next node (you can use distance from ground to next floor as cost of edges from dummy to that node) or climbing up carrying a number of kids from previous floors.