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

Автор jatinxkirito, история, 7 месяцев назад, По-английски

Can anybody please tell how do you handle this kind of questions. I can't seem to find a solution.

Fofo, the richest man in the city has a big problem and he believes that you are the only one capable of solving it. He has recently completed N projects and earned A[i] profit for every project. He now wants to build M warehouses such that each warehouse can accommodate K bundles of money. The money bundles must be distributed such that the following conditions are true: • The profit earned from a project is not distributed among more than one warehouse. • The warehouse can contain more than one project's profit, provided that the total number of bundles does not exceed K. Now he wants your help by determining the smallest value for K so that he can place all the bundles in the M warehouses. Find the smallest possible value of K such that the profit earned from all projects is distributed across the M warehouses.

Теги dp, help
  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by jatinxkirito (previous revision, new revision, compare).

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

i think we can solve this by binary search ,since for all the possible values of k ( greater than the minimum ) we can accomodate the bundles of money so we can see a monotonic graph which proves we can apply binary search.

»
7 месяцев назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Strongly NP-complete.

There are multiple approaches if the constraints are low enough for bitmask DP.

  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you please provide a reference

  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    From the article:

    On the other hand, bin packing is solvable in pseudo-polynomial time for any fixed number of bins K

    And in case of binary search

    solvable in polynomial time for any fixed bin capacity B

    • »
      »
      »
      7 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      "fixed" means it's treated like a constant in complexity analysis, for example $$$N^K$$$ is a polynomial for fixed $$$K$$$.

  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks a lot

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

infosys