JZTXT

背包问题

发布时间 2023-04-04 16:45:27作者: cxy8

01背包

糖果

这是一道有限制选择问题，可以类比01背包的思路来考虑这道题

WechatIMG828.png

#include <cstring>
#include <iostream>

using namespace std;
const int N = 110;
//用滚动数组进行空间的优化
int f[2][N], w[N], n, k;

int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; ++ i)    cin >> w[i];
    //将其他状态均设置为不合法状态，初始状态只有f[0][0] = 0
    memset(f, -0x3f, sizeof f);
    //错误的初始化方法，当一个都不选的话，mod k的余数只能是0
    // for(int i = 0; i < k; ++ i) f[0][i] = 0;
    f[0][0] = 0;
    for(int i = 1; i <=n ; ++ i)
        for(int j = 0; j < k; ++ j)
            f[i & 1][j] = max(f[(i - 1) & 1][j], f[(i - 1) & 1][(j  + k - w[i] % k) % k] + w[i]); 
    
    cout << f[n & 1][0] << endl;
    return 0;
}