算法分析

01背包问题

注意：由于都需要取模操作，并不是单调操作，因此不能从大到小简化到1维

时间复杂度 $O(nk)$

参考文献

蓝桥杯辅导课

Java 代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N = 110;
    static int INF = 0x3f3f3f3f;
    static int n;
    static int k;
    static int[][] f = new int[N][N];//从前i个物品中选，且总体积模k恰好是j的最大值
    static int mod(int x,int y)
    {
        return ((x % y) + y) % y;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        k = scan.nextInt();
        for(int i = 0;i <= n;i ++)Arrays.fill(f[i], -INF);
        f[0][0] = 0;
        for(int i = 1;i <= n;i ++)
        {
            int v = scan.nextInt();
            for(int j = 0;j < k;j ++)
            {
                f[i][j] = f[i - 1][j];
                f[i][j] = Math.max(f[i][j], f[i - 1][mod(j - v,k)] + v);
            }
        }
        System.out.println(f[n][0]);
    }
}