我在Codechef上看到了这个程序。
有N个包装袋,每个包装袋里面都有一些糖果。(例如:第一个包装袋里面有10个,第二个包装袋里面有4个,以此类推)
我们需要从中恰好选择M个包装袋(M≤N),使得其中的所有糖果数量能够被K整除。
如果存在多个解决方案,则输出其中糖果数量最少的那个。
我认为它与子集求和问题相似,但那是NP难题。所以将需要指数级时间。
我不需要完整的解决方案,但希望能得到一个算法。我已经思考了两天,但无法得出正确的逻辑。
1 ≤ M ≤ N ≤ 50000,1 ≤ K ≤ 20 每个包装袋中的糖果数量 [1,10^9]
我认为它与子集求和问题相似,但那是NP难题。所以将需要指数级时间。
我不需要完整的解决方案,但希望能得到一个算法。我已经思考了两天,但无法得出正确的逻辑。
1 ≤ M ≤ N ≤ 50000,1 ≤ K ≤ 20 每个包装袋中的糖果数量 [1,10^9]