vinayakawanti's blog

Minimum number of subsets with sum less than k

By vinayakawanti, history, 2 years 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

Comments Comments (4)
| Write comment?
»
2 years ago, # |
  Vote: I like it +27 Vote: I do not like it

I think this problem is worth 1 million dollars.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 years 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

→ Reply