n1e2m3's blog

help needed ... standard DP, Backtracking Problem
By n1e2m3, history, 6 years ago, In English

Problem :

This is the time of Christmas and Santa wants to distribute gifts to M children. He has N number of boxes, and each box contains some chocolates. Now, Santa wants to distribute N boxes to M children keeping in mind that distribution should be as fair as possible. To fairly distribute the gift boxes, Santa wants to minimize the maximum number of choclates gifted to a child.
Formally, given M number of children and N boxes, where each box contains some amount of chocolates. The task is to minimize the maximum number of chocolate gifted to a child.
In another word, you have to divide array into M subset such that maximum sum of subset is minimized.
Input:
First line of input contains number of testcases T. For each testcase, there will be three lines of input. First line contains N number of gift boxes, next line contains choclates in each of the N boxes. Last line contains number of children.
Output:
For each testcase, print the minimum number of maximum chocolate a child get.
Constraints:
1 <= T <= 100
1 <= N, M <= 10^6
1 <= A[i] <= 10^8

Example:
Input:
1
4
12 34 67 200
3

Output:
200

Explanation:
Testcase 1: Minimum 200 chocolates will be given to a child which gets the maximum number of chocolate.
Another Corner Case : n = 5 and M=3
array is : [ 3 4 5 5 8]
answer is : 9

how to solve? i didn’t figure out.

  • Vote: I like it
  • -8
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

Let's turn this into a decision problem — Is it possible to give at most k chocolates to each child? This is np-complete. Because we can reduce decision version of bin packing to this problem (just let a unit of weight be 1 chocolate and the bins be children, also let the capacity of all bins be k). Now the answer for the bin packing decision problem is yes iff the answer for the chocolate decision problem is yes.

If you can solve the original chocolate problem, it is trivial to solve its decision version. So this problem is not solvable (deterministically) with a polynomial time algo (unless P=NP).

→ Reply