这道题状态定义和转移与另外一道很相似传送门
这也是背包问题，有限制的组合问题。
所以二维状态，第一维是物品数量，第二维是限制。

1.状态定义：
$dp(i, j)$代表前$i$个物品总价值$ \%k=j $的集合,在这里限制是关于 $\%k$余数是多少。

2.转移方程：
$ dp(i, j) = max(dp(i - 1, j), dp(i - 1, (j - w[i]) \%k)+w[i]) $
我觉得这里用集合分析的方法分析更好，特别是在状态转移的时候，集合究竟由哪些子集合组成。
筛选标准：最后不同的一步（在这里是选不选这个物品）
不选的话：子集合都不包括第$i$个物品，表示的意义就是前$i-1$个物品，$\%k=j$的集合：$dp(i-1, j)$。
选择第$i$个物品：子集合都包括第$i$个物品，并且前面选择的商品和$S$满足$(S+a[i])\%k=j$，而我们需要从和这个$S$有关的集合，状态记录的都是$\%k$后的结果，所以我们只需要知道$S\%k (=(j-a[i])\%k)$的那个状态的值。

3.初始化：
$dp(0, 0) = 0, dp(0, i) (i \ne 0)$都是不合法的状态，所以必须要初始化为负无穷，不然的话可以选择先初始化第一件物品的所有情况，再迭代第二个物品之后 (仔细想想，如果不合法的状态初始化为0了，后面递推的时候，答案就会变大)

4.注意事项：
(1)转移方程中的$(j - w[i]) \%k)$可能为负的，必须要将余数变成$[0,n-1]$之间，所以$cpp$负数取余要变成$(j - w[i]) \%k+k)\%k$。

下面大致说明下正确性：
1.假如$(j - w[i] >= 0)$，由于$k\%k=0$，所以不会影响。
2.假如$(j - w[i] < 0)$, 带个负数进去试下就可以验证，在这里$+k$可以使$(j - w[i]) \%k$变成$[0,n-1]$之间，再取余仍然是$[0,n-1]$之间。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<stack>
#include<climits>
#define x first
#define y second
#define MP make_pair
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 100 + 5;
int n, k, w[N];
//dp(i, j)代表前i个物品 总价值%k=j的集合
int dp[N][N];

int main(void){
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> w[i];
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            dp[i][j] = INT_MIN;

    //dp(0 ,i) (i != 1)都是不存在的状态，所以必须要初始化为负无穷，不然的话可以选择先初始化第一件物品的所有情况，再迭代第二个物品之后
    //dp(i ,j) <-  max(dp(i - 1, j), dp(i - 1, (j - w[i]) % k) + w[i])
    // (s + w[i]) % k = j -> s % k = (j - w[i]) % k

    dp[0][0] = 0;
    for (int i = 1; i <= n; ++i){
        for (int j = 0; j <= k - 1; ++j)
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][((j - w[i]) % k + k) % k] + w[i]);
    }
    cout << dp[n][0];
    return 0;
}