C++

$\color{gold}{— > 蓝桥杯辅导课题解}$

思路：

dp 背包问题（选择模型）

                                            闫氏dp分析法

                集合：所有从前i个物品中选，且总和除k余数为j的所有方案
    状态表示                                                                    化零为整
    f[i][j]     属性：最大值max
dp 

    状态计算    集合的划分---f[i][j]
                                不包含物品i：f[i - 1][j]                        化整为零
                                包含物品i：f[i - 1][(j - w) % k] + w
                转移方程：  f[i][j] = max(f[i - 1][j], f[i - 1][(j + k - w % k) % k] + w)

$code$

#include <bits/stdc++.h>
using namespace std;

const int N = 110;

int n, k;
int f[N][N];

int main() {
    cin >> n >> k;

    memset(f, -0x3f, sizeof f); // 初始化，表示前i个取模为k的方案不存在，此时不应该考虑这个集合
    // 而之所以初始化为负无穷是因为无论怎么凑都凑不出负无穷这个数

    f[0][0] = 0;
    for (int i = 1; i <= n; i ++) {
        int w;
        cin >> w;
        for (int j = 0; j < k; j ++) 
            f[i][j] = max(f[i - 1][j], f[i - 1][(j + k - w % k) % k] + w);
            // 之所以要 (j + k - w % k) % k 是为了防止负数的出现
            // w % k 是一个 <= k - 1 的数，k减一个小于等于 k-1一定是个正数
    }

    cout << f[n][0];

    return 0;
}