糖果
题目分析
从N件糖果产品中选择若干件,每件产品所含的糖果数量不同。要求是:选择的所有产品包含的糖果总数是K的倍数且糖果数量是最多的。
使用方法
- 闫氏dp分析法
如下图所示:
核心要点分析
- 初始化:
f[0][0]=0,f[0][i](i!=0)
都是不合法的状态,所以必须初始化为负无穷,如果不合法状态初始化为0,在后续递推过程中,答案就会变大。 - 转移方程中的
((j-w[i])%k+k)%k
由来:举个例子,j = 99,k=100,w[i]=1000。此时(j-w[i])%k
= -1;还是负数(但是再计算器中是正数)需要加上k变成正数后再取模,余数变成正数。(利用同余定理:x%mod=(x+mod)%mod
)
实现代码
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 110;
int n,k;
int f[N][N];
int w[N];
int main()
{
scanf("%d%d",&n,&k);
for (int i = 1 ;i <= n ;i ++) scanf("%d",&w[i]);
for(int i=0;i<k;i++)f[0][i]=-1e9;
f[0][0]=0;
for (int i = 1;i <= n; i++) // 枚举产品种类
for (int j = 0; j < k; j ++) // 枚举产品中糖果%k后的个数
{
f[i][j] = max(f[i-1][j],f[i-1][((j-w[i])%k+k)%k]+w[i]);
}
printf("%d\n",f[n][0]);
return 0;
}