AcWing|AcWing 1047. 糖果

题目链接
题目描述:
由于在维护世界和平的事务中做出巨大贡献,Dzx被赠予糖果公司2010年5月23日当天无限量糖果免费优惠券。
在这一天,Dzx可以从糖果公司的 N 件产品中任意选择若干件带回家享用。
糖果公司的 N 件产品每件都包含数量不同的糖果。
Dzx希望他选择的产品包含的糖果总数是 K 的整数倍,这样他才能平均地将糖果分给帮助他维护世界和平的伙伴们。
当然,在满足这一条件的基础上,糖果总数越多越好。
Dzx最多能带走多少糖果呢?
注意:Dzx只能将糖果公司的产品整件带走。
【AcWing|AcWing 1047. 糖果】题目大意:给N件物品,选择其中某些件,使它们的总和是K的倍数。(选择模型为背包问题)
解决方法:DP
集合:所有从前i个物品中选,且总和除以k的余数是j的所有方案
集合划分:
AcWing|AcWing 1047. 糖果
文章图片

#include #include using namespace std; const int N = 110; int n, k; int f[N][N]; int max(int x, int y) { return x > y ? x : y; }int main() { scanf("%d%d", &n, &k); memset(f, -0x3f, sizeof f); f[0][0] = 0; for (int i = 1; i <= n; i ++ ) { int w; scanf("%d", &w); for (int j = 0; j < k; j ++ ) f[i][j] = max(f[i - 1][j], f[i - 1][(j + k - w % k) % k] + w); //余数应为正数 }printf("%d\n", f[n][0]); return 0; }

    推荐阅读