I_love_victor's blog

By I_love_victor, history, 5 weeks ago, In English

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!!!

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

I dont now

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

its easy problem

»
5 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Yes

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks bro

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What are constraints of the problem, can you give full statement?

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

code: https://pastebin.com/VPAfgV2s

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

No problem but you may pay me 50$ or maybe 100$,I don'y know now but I will think about it,ok bye.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it