AcWing 1047.糖果

题目链接：

https://www.acwing.com/problem/content/1049/

题目大意：

n 个数字，可以选择其中的若干个，要求它们的和是 k 的倍数，求最大的和为多少

思路：

因为每选择一个物品的状态可以由上一个状态转移过来，于是想到 dp，就是一个 01背包，我们将一个物品放入背包中，最后背包的容量为 k 的倍数，数字 * k 之后很大，于是想到 取模。
dp[i][j] 中的 i 为第 i 件物品，j 为和 %k 后的结果，写出 01背包。

代码：

#include 
using namespace std;
const int N = 105;
int w, n, k, dp[N][N];
int main(){
	cin >> n >> k;
	for (int i = 0; i <= n; i++)
		for (int j = 0; j < k; j++)
			dp[i][j] = INT_MIN;
	dp[0][0] = 0;  //不放数的时候结果为 0
	for (int i = 1; i <= n; i++){
		scanf("%d", &w);
		for (int j = 0; j <= k - 1; j++)
			dp[i][j] = max(dp[i - 1][j], dp[i - 1][((j - w) % k + k) % k] + w);
	}
	cout << dp[n][0] << "\n";
	return 0;
}