选择DP模型:背包问题
题目关键:
- 集合:
从前i个物品中选,且总体积%k恰好是j的方案
- 集合属性值:
Max
本题与0-1背包模型类似的状态转移方程:
f[i][j]=max(f[i-1][j],f[i-1][((j-w)%k+k)%k]+w);
注意:这里的f[i-1][((j-w)%k+k)%k]+w)是为了求得余数为正数才这样写,因为cpp负数求模还是负数
#include <cstdio>
#include <cstring>
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;
}