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 :)
Auto comment: topic has been updated by its_ulure (previous revision, new revision, compare).
Along these lines I suppose. Could you please give a link to submit?
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 :)
Ah, ok. Feel free to ask any questions.
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.
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.
Indeed. geniucos below has pointed out that it's an NP-hard problem.
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.