余数枚举

步骤

1. 读入数字，并将其按对K取模的结果存到对应的数组0~K-1里 nums.get(num % K).add(num)
2. 因为要求总和最大，所以在余数相同的情况下，优先选用较大的数字，故对每个数组降序排列
3. 枚举前两个数的余数，从而计算到第三个数的余数，按照余数从对应数组中找到最大的几个数，求出总和
4. 所有求出的总和的最大值即为最终结果
5. 注意：
   • 选择时要先判断该数组是否有足够的元素可供选择
   • 每次选择的数字都是某余数对应数组的前面（最大的）几个元素
   • 枚举出来的三个余数有可能出现多个相等的情况，即在一个数组里可能会选取前两个或着前三个
6. 时间复杂度$O(K^2)$

代码

import java.lang.*;
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static int n, K;
    static ArrayList<ArrayList<Integer>> nums = new ArrayList<>();

    public static void main(String[] args) {
        n = scanner.nextInt();
        K = scanner.nextInt();
        for (int i = 0; i < K; i++) {
            nums.add(new ArrayList<>());
        }
        for (int i = 1; i <= n; i++) {
            int num = scanner.nextInt();
            nums.get(num % K).add(num);  // 按%K的结果存到对应ArrayList里
        }
        for (int i = 0; i < K; i++) {
            ArrayList<Integer> arr = nums.get(i);
            arr.sort((o1, o2) -> o2 - o1);  // 降序排列
        }
        int ans = 0;  // 存最终答案 数字总和
        for (int i = 0; i < K; i++) {  // 枚举第一个数的余数
            for (int j = 0; j < K; j++) {  // 枚举第二个数的余数
                int k = ((K - i - j) % K + K) % K;  // 计算第三个数的余数
                if (i == j && j == k) {  // 如果三个数的余数都相等
                    ArrayList<Integer> arr = nums.get(i);  // 那么它们属于同一个ArrayList
                    if (arr.size() >= 3) {  // 当本数组元素个数大于三时可用
                        ans = Math.max(ans, arr.get(0) + arr.get(1) + arr.get(2));
                    }
                } else if (i == j || j == k || i == k) {  // 如果有且仅有两个余数是相等的
                    ArrayList<Integer> arr1, arr2;
                    arr1 = nums.get(i == j || i == k ? i : j);  // 获取相等的那对余数值
                    arr2 = nums.get(i == j ? k : (i == k ? j : i));  // 获取剩下的那个余数值
                    // 相等的余数 对应数组元素不少于2个 另一个余数对应数组元素不少于1个
                    if (arr1.size() >= 2 && arr2.size() >= 1) {
                        ans = Math.max(ans, arr1.get(0) + arr1.get(1) + arr2.get(0));
                    }
                } else {  // 如果三个都不等
                    ArrayList<Integer> arr1 = nums.get(i), arr2 = nums.get(j), arr3 = nums.get(k);
                    if (arr1.size() > 0 && arr2.size() > 0 && arr3.size() > 0) {  // 三个余数对应数组元素个数均大于0
                        ans = Math.max(ans, arr1.get(0) + arr2.get(0) + arr3.get(0));
                    }
                }
            }
        }
        System.out.println(ans);
    }
}

背包解法

要点

1. 每个数只能选一次，01背包；每次考虑前i个数，引入一个维度用于区分i；从i个数中找到3个数，引入一个维度用于记录“当前已选的个数”，最大值为3；“和是K的倍数”引入一个维度用于记录“总和%k的值”，参考AcWing 1047. 糖果（Java）
2. 状态表示共计3个维度，$f(i,j,k)$意为“只考虑前$i$个数、已选了$j$个数且$总和\ mod\ K$结果为$k$”的选法集合，属性为$Max$
3. 状态计算
   • 不选：$f(i,j,k) = f(i-1,j,k)$
   • 选：$f(i,j,k) = f(i-1, j-1, (k-w\ mod\ K+K)\ mod\ K) + w)$
   • 综上：$f(i,j,k) = max(f(i-1,j,k), f(i-1, j-1, (k-w\ mod\ K+K)\ mod\ K) + w)$
   • 观察到第$i$个的状态只与$i-1$的状态和当前数字有关，故第一维空间可以优化，转为$f(j,k)$。注意空间优化后对$j$的循环要逆序
4. 状态初始化为$f(i,0,0)=0$表示“考虑前$i$个数、已选了$0$个数且$总和\ mod\ K=0$”的选法的数字总和为$0$（啥都没选）；因为属性为$Max$，所以其它位置初始化为一个极小的数（负无穷）
5. 引入贪心策略：最特殊的情况是“三个数都选了%K=X的集合”，要求总和最大，故本情况肯定优先使用集合中最大的三个数。因此，对于余数分别为0~(K-1)的集合，只需保留各自集合中前三大的数（不足三个取全部），共计最多3K个
   • 朴素做法时间复杂度$O(n\*3\*K)=O(3\*10^8)$，贪心优化后$O(3K\*3\*K)=O(9\*10^6)$

代码

import java.lang.*;
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static int n, K;
    // f(i,j,k) = max(f(i-1,j,k), f(i-1,j-1,(k-num%K+K)%K) + num)
    static int[] a = new int[3010];
    static int[][] f = new int[4][1010];
    static ArrayList<ArrayList<Integer>> nums = new ArrayList<>();

    public static void main(String[] args) {
        n = scanner.nextInt();
        K = scanner.nextInt();
        // 初始化nums数组 其中包含k个元素 第i个用于存（%K=i）的数字
        for (int i = 0; i < K; i++) {
            nums.add(new ArrayList<>());
        }
        // 读取数字 模K 按余数存数字到对应的ArrayList
        for (int i = 1; i <= n; i++) {
            int num = scanner.nextInt();
            nums.get(num % K).add(num);
        }
        // 贪心 对于余数0~(k-1)的每种只需取最大的三个数
        // 对每种余数集合中的数字 先降序排列 再取前三个 不足三个取全部
        // 最多3K个数字 存入a[1]~a[pos-1]   (pos-1 <= 3K)
        int pos = 1;
        for (int i = 0; i < K; i++) {
            ArrayList<Integer> arr = nums.get(i);
            arr.sort((o1, o2) -> o2 - o1);
            for (int j = 0, len = Math.min(3, arr.size()); j < len; j++) {
                a[pos++] = arr.get(j);
            }
        }
        // 集合赋初始值为一个极小数 因为所求属性为max
        for (int i = 0; i < 4; i++) {
            Arrays.fill(f[i], Integer.MIN_VALUE);
        }
        // 不考虑任何数字、已取了0个数且总和%K=0的状态 值（数字总和）为0
        f[0][0] = 0;
        // 遍历所有待选数字 ==> 遍历已选的数（注意这里优化了第一维的空间 01背包循环要逆序） ==> 枚举余数
        for (int i = 1; i < pos; i++) {
            for (int j = 3; j > 0; j--) {
                for (int k = 0; k < K; k++) {
                    f[j][k] = Math.max(f[j][k], f[j - 1][((k - a[i] % K + K) % K)] + a[i]);
                }
            }
        }
        System.out.println(f[3][0]);
    }
}