思路与算法

dp[r]表示已处理商品中，选取总糖果数模K等于r时的最大总数，不可达记-1。初始dp[0]=0。处理糖果x时复制上一层为next表示不取，再从所有可达r向(r+x)%K更新dp[r]+x表示取，最后换成新层。输出dp[0]。

正确性说明

对每件产品只有取或不取两种选择，转移完整覆盖全部合法子集。固定余数只保留最大和是安全的，因为之后再取同一批产品时余数变化相同、较大和始终更优。两层数组确保每件产品至多取一次。初始空集提供0，也是无法获得正倍数时的正确输出。

复杂度

N≤100、K≤100，时间O(NK)，空间O(K)。每轮复制及初始化next为O(K)，已包含在时间内；初始数组O(K)。最大糖果总数10^8，程序仍用long long。独立答案使用任意精度可达和位集，不复用余数最大值DP。

易错点

不能原地更新后再次读取同一轮新增状态，这会重复拿一件商品。模0余数允许空集0，其他余数初始不可达。要求输出总数而不是件数或方案数。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<long long> dp(k, -1);
    dp[0] = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        auto next = dp;
        for (int j = 0; j < k; ++j)
            if (dp[j] >= 0)
                next[(j + x) % k] = max(next[(j + x) % k], dp[j] + x);
        dp.swap(next);
    }
    cout << dp[0] << '\n';
}