vinayakawanti's blog

By vinayakawanti, history, 16 months ago, In English

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.

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

| Write comment?
»
16 months ago, # |
  Vote: I like it +27 Vote: I do not like it

I think this problem is worth 1 million dollars.

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It is a variation of the NP-complete Bin Packing problem.

»
16 months ago, # |
  Vote: I like it +13 Vote: I do not like it

As long as $$$K \geq \max{W_i}$$$ you can use one aircraft and then come back for more people