01背包变形问题

如样例，对于每个密码来说

$ 时间复杂度O(NK)，空间复杂度O(NK) $
因为是%k,不能保证每个层状态j使用的状态一定是上一层前面的或者后面的,故不能压缩空间

参考文献

蓝桥杯辅导课

AC代码

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e3 + 10;

int f[N][N];
int n, k;

int main(){
    cin >> n >> k;

    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;
    for (int i = 1 ; i <= n ; i ++){
        int w;
        cin >> w;
        for (int j = 0 ; j < k ; j ++){
            f[i][j] = f[i - 1][j];
            f[i][j] = max(f[i][j], f[i - 1][(j + k - w % k) % k] + w);
        }
    }
    cout << f[n][0];
    return 0;
}