转移方程

转移方程的核心思想是 选择和不选择当前物品 两种情况的比较。具体来说：

不选择当前物品：

• 如果不选择第 i 个物品，那么 dp(i, j) 就等于 dp(i-1, j)，即前 i-1 个物品中，满足 总价值 % k == j 的最大和。

选择当前物品：

• 如果选择第 i 个物品，那么就要计算 dp(i-1, (j - w[i]) % k)，即前 i-1 个物品中，选择的物品总价值 S 满足 S % k = (j - w[i]) % k，然后加上当前物品的价值 w[i]。
• 注意：为了保证取模后的结果在 [0, k-1] 范围内，需要进行 ((j - w[i]) % k + k) % k 这样的操作，确保负数取模后变为正数。
• #include<bits/stdc++.h>
  using namespace std;
  const int N=1e2+10;
  int a[N],f[N][N];
  int main ()
  {
      int n,m;
      cin>>n>>m;
      for(int i=1;i<=n;i++)
      {
          cin>>a[i];
      }
      for(int i=0;i<N;i++)
      {
          for(int j=0;j<N;j++)
          {
              f[i][j]=INT_MIN;
          }
          
      }
      f[0][0]=0;
      for(int i=1;i<=n;i++)
      {
          for(int j=0;j<m;j++)
          {
              f[i][j]=max(f[i-1][j],f[i-1][((j-a[i])%m+m)%m]+a[i]);
          }
      }
      cout<<f[n][0]<<endl;
      return 0;
  }