我在codechef上看过这个节目。
有N包，每包都有一些糖果。（例如：1包含10，2包含4等等）
我们必须从中精确地选择m个包（m如果有多个解决方案，则输出糖果数量最少的解决方案。
我认为它类似于子集和问题，但这是np难的。所以这需要指数时间。
我不想要这个程序的完整解决方案。一个算法将是可取的。从2天开始思考，但无法得到正确的逻辑。
1≤m≤n≤50000，1≤k≤20
每包糖果的数量[1,10^9]
最佳答案
让packets包含原始数据包。
将k划分为p = 1, 2, ..., m个数>= 1和< k的和（有O(2^k)这样的划分）。对于每个分区，遍历packets并添加那些余数模k是分区元素之一的数字，然后从分区中删除该元素。同时保持最小和，并更新全局最小值。注意，如果m > p，则还必须有m - p零。
您可能认为这是O(2^k * n)并且太慢了，但是如果您保持packets，实际上不必为每个分区迭代num[i] = how many numbers have packets[i] % k == i数组，在这种情况下，它变成O(2^k + n)。为了处理最小和要求，您可以保持num[i] = the list of the numbers that have packets[i] % k == i，这将允许您始终为有效分区选择最小的数字。