(dp)

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=110;
int n,m,k;
int a[N];
int f[N][N];
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
     memset(f,-9,sizeof f);
     f[0][0]=0;//初始条件
    for(int i=1;i<=n;i++)
    for(int j=0;j<k;j++)
    {
        f[i][j]=max(f[i-1][j],f[i-1][(j-a[i]%k+k)%k]+a[i]);
        //在i件产品中选择的糖果总数目模k等于j的糖果总数
        //分类条件：第i件选或不选
        //(j-a[i])%k结果可能为负数  则对其优化
    }

    cout<<f[n][0]<<endl;//结果是在n件产品中挑选总数模k==0的总数
    return 0;
}