help needed ... standard DP, Backtracking Problem

Revision en4, by n1e2m3, 2019-05-29 08:33:12

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.

Tags #dynamic-programming, #backtracking, hard problem

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English n1e2m3 2019-05-29 08:33:12 1
en3 English n1e2m3 2019-05-28 20:11:35 104
en2 English n1e2m3 2019-05-28 20:10:04 16
en1 English n1e2m3 2019-05-28 20:09:05 1422 Initial revision (published)