vinayakawanti's blog

Minimum number of subsets with sum less than k

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

»
2 months ago, # |
  Vote: I like it +27 Vote: I do not like it

I think this problem is worth 1 million dollars.

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

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

    that's brilliant, but what if it's a one time use aircraft ?

    → Reply