Choosing M from N packets, the sum sum is minimal for K

Question

I saw this program on Codechef. There are N packets, each of which contains candy. (For example: 1st contains 10, 2nd contains 4 and so on) We must choose exactly M packets from it (M <= N) so that the total candies are divided by K. If there is more than one solution, then print the one which has the lowest amount of candy.

I thought this seemed like a Subset Sum problem, but this NP is hard. Thus, it will take an exponential time.

I do not want a complete solution to this program. The algorithm will be appreciated. Thinking about it from 2 days, but not able to get the correct logic.

1 ≤ M ≤ N ≤ 50,000, 1 ≤ K ≤ 20 The number of sweets in each bag [1,10 ^ 9]

Answer 1

Let packets contain the source packets.

The division of k into the sums p = 1, 2, ..., m numbers >= 1 and < k (there are such O(2^k) such sections). For each section, iterating over packets and add those numbers, the rest modulo k is one of the elements in the section, and then remove this element from the section. Keep the minimum amount and update the global minimum. Note that if m > p , you must also have m - p zeros.

You might think that this is O(2^k * n) and it is too slow, but in fact you do not need to iterate over the packets array for each section if you save num[i] = how many numbers have packets[i] % k == i , in which case it becomes O(2^k + n) . To cope with the minimum amount requirement, you can save num[i] = the list of the numbers that have packets[i] % k == i , which allows you to always select the smallest numbers for a valid section.

Answer 2

Take another look at http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution and note that K is relatively small. In addition, although N can be large, all you care about in the sums that are related to N is the response mode of K. So there is a dynamic programming solution where at each step you have K possible values ​​of mod K, and you keep track of which of these values ​​is currently achievable.