### I_love_victor's blog

By I_love_victor, history, 6 weeks ago,

In Chapter DP from permutations to subsets, there is a problem about elevators. There is an elevator with maximum weight x, and n people with known weights who want to get from the ground floor to the top floor. What is the minimum number of rides needed if the people enter the elevator in an optimal order? Help me!!!

• 0

 » 6 weeks ago, # |   +21 I dont now
 » 6 weeks ago, # |   0 its easy problem
•  » » 6 weeks ago, # ^ |   0 Noob
 » 6 weeks ago, # |   +5 Yes
 » 6 weeks ago, # |   0 thanks bro
 » 6 weeks ago, # |   0 What are constraints of the problem, can you give full statement?
•  » » 6 weeks ago, # ^ |   0 n <= 20 and x <= 10^9
•  » » 6 weeks ago, # ^ |   0
 » 6 weeks ago, # |   +3 You can solve it by dp on submasks (I got it accepted). Define F(mask,last) — pair(number of elevators needed to move all people that mask include, space occupied in the last elevator). We want to make this pair as small as possible (at first we want to have smallest number of elevators (we can always summon one more elevator with 0 occupied space), if it's equal we want to have as much free space in last elevator as possible). We will iterate through all people, whom included in mask, and try to relaxate dp[mask] trough dp[submask], where submask = mask xor (2^last). At first try to add last passenger to an existing elevator. If it's impossible — summon one more elevator and put it there.
 » 3 weeks ago, # |   0 No problem but you may pay me 50$or maybe 100$,I don'y know now but I will think about it,ok bye.
•  » » 3 weeks ago, # ^ |   0 don't worry about it ok olimpic_boy,ok bye.