Batyrow's blog

By Batyrow, history, 6 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?

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?

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

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

Auto comment: topic has been updated by Batyrow (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it -18 Vote: I do not like it

It is correct solution. I dont find counterexample.

»
6 weeks ago, # |
Rev. 6   Vote: I like it +18 Vote: I do not like it

Maybe you greedy-algorithm is wrong.

The number of people is $$$10$$$.

$$$5$$$ people wighted $$$23$$$ and $$$5$$$ people wighted $$$6$$$. Maximum weight $$$x$$$ is $$$33$$$.

You will choose $$$6$$$ times:

$$$(6,6,6,6,6)$$$

$$$(23)$$$

$$$(23)$$$

$$$(23)$$$

$$$(23)$$$

$$$(23)$$$

Maybe I can choose $$$5$$$ times:

$$$(6,23)$$$

$$$(6,23)$$$

$$$(6,23)$$$

$$$(6,23)$$$

$$$(6,23)$$$