选择N个数据包中的M个，使它们的总和为K的最小倍数。

Question

选择N个数据包中的M个，使它们的总和为K的最小倍数。

4

我在Codechef上看到了这个程序。有N个包装袋，每个包装袋里面都有一些糖果。（例如：第一个包装袋里面有10个，第二个包装袋里面有4个，以此类推）我们需要从中恰好选择M个包装袋（M≤N），使得其中的所有糖果数量能够被K整除。如果存在多个解决方案，则输出其中糖果数量最少的那个。

我认为它与子集求和问题相似，但那是NP难题。所以将需要指数级时间。

我不需要完整的解决方案，但希望能得到一个算法。我已经思考了两天，但无法得出正确的逻辑。

1 ≤ M ≤ N ≤ 50000，1 ≤ K ≤ 20 每个包装袋中的糖果数量 [1,10^9]

- dejavu

1 ≤ M ≤ N ≤ 50000，1 ≤ K ≤ 20。 - dejavu

1

@AndroidDecoded问题的标题不太好，请修正。例如，“选择M个N数据包，使得它们的和是K的最小倍数”。 - James Waldby - jwpat7

完成了。谢谢。是的，标题不好。 - dejavu

2个回答

0

再次查看http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution，注意K相对较小。此外，尽管N可能很大，但在涉及N的总和中，您关心的只是答案mod K。因此，在这里潜藏着一种动态规划解决方案，每个步骤都有K个可能的mod K值，并且您跟踪哪些值当前可达。

- mcdowella

在看过M之后，我认为状态空间更大了，但问题仍然可解决：循环i从1到N，在每一步中跟踪哪些组合（结果对K取模，使用恰好m个数据包）是可达的，使用的数据包编号为1到i。利用i-1时的可达组合来计算i时的可达组合。 - mcdowella

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- IVlad · Accepted Answer

让数据包包含原始数据包。

将k分成p = 1, 2, ..., m个数字的和，这些数字>= 1且< k（有O(2^k)这样的分区）。对于每个分区，遍历数据包并添加那些余数模k是分区元素之一的数字，然后从分区中删除该元素。同时保持最小和，并更新全局最小值。请注意，如果m > p，您还必须有m - p个零。

你可能认为这是O(2^k * n)，速度太慢了，但实际上如果你保持num[i] = 有多少个数字满足 packets[i] % k == i，那么你就不必为每个分区迭代packets数组，这样时间复杂度就变成了O(2^k + n)。为了处理最小和的要求，你可以保持num[i] = 具有 packets[i] % k == i 的数字列表，这将允许你始终选择有效分区中最小的数字。