糖果题解（01背包）

题目连接

题目大意

给你n个数，你要选择任意数量的数使得这些的和为k的倍数，求最大的和

题目思路

设 dp[ i ] [ j ] 为前i数中选任意的数使得sum%k=j，dp[ i ] [ j ]代表max sum

然后就是01的思路了

代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e2+5,inf=0x3f3f3f3f;
int n,k;
int a[maxn],dp[maxn][maxn];
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<k;j++){
            if(j==0){
                dp[i][j]=0;
            }else{
                dp[i][j]=-inf;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<k;j++){
            dp[i][j]=max(dp[i-1][((j-a[i])%k+k)%k]+a[i],dp[i-1][j]);
        }
    }
    printf("%d\n",dp[n][0]);
    return 0;
}