次のような動的計画法を考えます。

• \(\mathrm{dp}_{i,j,k}\) : \(a_1,\ldots,a_i\) から \(j\) 個が選ばれていて、総和を \(D\) で割った余りが \(k\) であるようなときの総和の最大値(不可能なら \(-1\) )

すると、答えは \(\mathrm{dp}_{N,K,0}\) です。

遷移は、\(a_i\) を選ぶ場合と選ばない場合を考えます。前者では \(j\) が \(1\) 増え、\(k\) も\(a_i\) の値に応じて変わります。後者では \(j,k\) がともに変わりません。

より詳細には実装例を参考にしてください。

実装例 (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    
	int N,K,D;
	cin>>N>>K>>D;
	
	vector<int> a(N);
	for(int i=0;i<N;i++)cin>>a[i];
	
	vector dp(N+1,vector(K+1,vector<long long>(D,-1)));
	dp[0][0][0] = 0;
	
	for(int i=0;i<N;i++){
		for(int j=0;j<K+1;j++){
			for(int k=0;k<D;k++){
				if(dp[i][j][k]==-1)continue;
				
				//a_i を選ばない場合の遷移
				dp[i+1][j][k] = max(dp[i+1][j][k],dp[i][j][k]);
				
				//a_i を選ぶ場合の遷移
				if(j!=K){
					dp[i+1][j+1][(k+a[i])%D] = max(dp[i+1][j+1][(k+a[i])%D],dp[i][j][k] + a[i]);
				}
			}
		}
	}
	
	cout<<dp[N][K][0]<<endl;
	
	return 0;
}