Competitive Programmes's Handbook problem

Правка en1, от Bacterium_, 2021-10-22 12:14:24

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?

I found one solution, it is to find the subset of people with maximum weight we can send every time and send those elements. I think it's time complexity works for n <= 20. It seems incorrect but I couldn't find any counterexample. Is there any counterexample?

Теги cph, counterexamples

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский Bacterium_ 2021-12-01 11:09:51 2 Reverted to en1
en2 Английский Bacterium_ 2021-10-22 12:16:38 2
en1 Английский Bacterium_ 2021-10-22 12:14:24 615 Initial revision (published)