### vinayakawanti's blog

By vinayakawanti, history, 2 months ago,

Capacity of an aircraft is K, you have N people with weights Wi. Find minimum number of air-crafts to transport all these people.

n <= 10^5 and k <= 10^9

How to approach this problem.

• +12

 » 2 months ago, # |   +27 I think this problem is worth 1 million dollars.
 » 2 months ago, # |   0 It is a variation of the NP-complete Bin Packing problem.
•  » » 2 months ago, # ^ |   0 Thanks!
 » 2 months ago, # |   +13 As long as $K \geq \max{W_i}$ you can use one aircraft and then come back for more people
•  » » 2 months ago, # ^ |   0 that's brilliant, but what if it's a one time use aircraft ?