Блог пользователя vinayakawanti

Minimum number of subsets with sum less than k

Автор vinayakawanti, история, 2 года назад, По-английски

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 года назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

I think this problem is worth 1 million dollars.

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

→ Ответить