its_ulure's blog

DP problem..
By its_ulure, history, 7 years ago, In English

I came across a problem few days ago. The problem states that given a set of n numbers , we need to divide the set into k groups (where, 1<=k<n)) such that the maximum product(of the numbers) in all the possible groups is minimal. Thanks in advance :)

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +2 Vote: I do not like it

Along these lines I suppose. Could you please give a link to submit?

Code
→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually I don't have the link, my friend asked me about it some days back, and thereby failing to solve this problem, I had to ask it in the forum. Anyways thanks for the solution :)

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Ah, ok. Feel free to ask any questions.

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 5   Vote: I like it 0 Vote: I do not like it

      This solution in incorrect, see comments below

      If the groups may not be contiguous, you can use a greedy process: sort the numbers in descending order and maintain current group products (initially 1s). Iterate through your numbers and add current number to the least product (greediness here). When updating the groups keep the max product which will be the answer.

      Code
      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Seems wrong to me.

        Imagine we have 5, 3, 2, 2, 2, 2 and k = 2.

        Ok so we have now a set {1, 1}

        And it changes:

        {5, 1}, {5, 3}, {5, 6}, {10, 6}, {10, 12} and finally {20, 12},so the answer is 20.

        But the optimal solution is {5, 3} and {2, 2, 2, 2} so the answer is 16.

        → Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Let a[i] = lg (a[i]). Let's binary search the answer Q, and let V = lg(Q). Now, we've reduced the problem to Bin Packing Problem which is known to be NP. This is a one-way reduction, but we're actually interested in the other direction: assume there is a solution to the problem that runs in polynomial time. This means that you can find for every 1<=K<=N, also in polynomial time (times N to be precise) the minimum V=lg(Q), which in turns means that for every real value V, we can now easily say what is the minimum K (number of bins) to pack the objects in containers of size V.

→ Reply