算法1

思路：背包问题，关于如何判断是背包问题，其实就是组合问题求最优解

C++ 代码

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1010;
int n,m;
vector <int> a[N];
int f[4][N];

int main()
{

  scanf("%d%d",&n,&m);
  for(int i=0;i<n;i++)
  {
      int x;
      scanf("%d",&x);
      a[x%m].push_back(x);//vector里面把数存到容器里面用.push_back
  }
    memset(f,-0x3f,sizeof f);//把所有状态初始化为负无穷
    f[0][0]=0;//当j为0，f[i][j],i表示从前i个数中选，j表示已经选了j件物品，当j为0，初试状态就为0

    for(int i=0;i<m;i++)//枚举所有物品
    {
       sort(a[i].begin(),a[i].end());
       reverse(a[i].begin(),a[i].end());//先排序，然后转置，选择最大的三个能构成k的倍数的数即可
       //天哪，这里还需要不能大于a[i].size(),否则就会边界报错，绝绝子
       for(int u=0;u<3&&a[i].size();u++)//最多是三维，原本是f[i][j][k],但是由于时间复杂度，优化如下
       {
           int x=a[i][u];
           for(int j=3;j>=1;j--)
            for(int k=0;k<m;k++)
                f[j][k]=max(f[j][k],f[j-1][(k-x%m+m)%m]+x);//核心是这一步
       }
    }
    printf("%d\n",f[3][0]);
    return 0;
}