解题思路

  1. 问题分析:

    • 需要从数组中选择一些数,使其和为 的倍数且最大
    • 可以转化为求模运算的动态规划问题
    • 对于每个数,可以选择或不选择
  2. 动态规划设计:

    • 状态定义: 表示考虑前 个数,和除以 时的最大值
    • 状态转移:
      • 不选第 个数:
      • 选第 个数:
    • 最终答案:,如果为 则说明无解
  3. 实现要点:

    • 注意处理余数为负数的情况
    • 使用 防止溢出
    • 初始化时要设置为负无穷,避免无解情况的干扰

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long maxKDivisibleSum(int n, int k, vector<int>& nums) {
    // dp[i][j]表示前i个数中选择一些数,和除以k余j的最大值
    vector<vector<long long>> dp(n + 1, vector<long long>(k, -1e18));
    dp[0][0] = 0;  // 初始状态
    
    // 遍历每个数
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < k; j++) {
            if(dp[i][j] == -1e18) continue;
            // 不选第i个数
            dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
            // 选第i个数
            int new_mod = (j + nums[i] % k) % k;
            dp[i+1][new_mod] = max(dp[i+1][new_mod], dp[i][j] + nums[i]);
        }
    }
    
    return dp[n][0] <= 0 ? -1 : dp[n][0];
}

int main() {
    int n, k;
    cin >> n >> k;
    
    vector<int> nums(n);
    for(int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    cout << maxKDivisibleSum(n, k, nums) << endl;
    return 0;
}
import java.util.*;

public class Main {
    public static long maxKDivisibleSum(int n, int k, long[] nums) {
        // dp[j]表示余数为j的最大和
        long[] dp = new long[k];
        long[] newDp = new long[k];
        Arrays.fill(dp, Long.MIN_VALUE);
        dp[0] = 0;  // 初始状态
        
        // 遍历每个数
        for(int i = 0; i < n; i++) {
            Arrays.fill(newDp, Long.MIN_VALUE);
            for(int j = 0; j < k; j++) {
                if(dp[j] == Long.MIN_VALUE) continue;
                // 不选第i个数
                newDp[j] = Math.max(newDp[j], dp[j]);
                // 选第i个数
                int new_mod = (int)((j + nums[i] % k) % k + k) % k;  // 处理负数
                newDp[new_mod] = Math.max(newDp[new_mod], dp[j] + nums[i]);
            }
            // 更新dp数组
            long[] temp = dp;
            dp = newDp;
            newDp = temp;
        }
        
        return dp[0] <= 0 ? -1 : dp[0];
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        
        long[] nums = new long[n];
        for(int i = 0; i < n; i++) {
            nums[i] = sc.nextLong();  // 使用nextLong()而不是nextInt()
        }
        
        System.out.println(maxKDivisibleSum(n, k, nums));
        sc.close();
    }
}
def max_k_divisible_sum(n: int, k: int, nums: list) -> int:
    # dp[i][j]表示前i个数中选择一些数,和除以k余j的最大值
    dp = [[-float('inf')] * k for _ in range(n + 1)]
    dp[0][0] = 0  # 初始状态
    
    # 遍历每个数
    for i in range(n):
        for j in range(k):
            if dp[i][j] == -float('inf'):
                continue
            # 不选第i个数
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
            # 选第i个数
            new_mod = (j + nums[i] % k) % k
            dp[i+1][new_mod] = max(dp[i+1][new_mod], dp[i][j] + nums[i])
    
    return -1 if dp[n][0] <= 0 else dp[n][0]

def main():
    n, k = map(int, input().split())
    nums = list(map(int, input().split()))
    print(max_k_divisible_sum(n, k, nums))

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法:动态规划
  • 时间复杂度:,其中 是数组长度, 是给定的除数
  • 空间复杂度:,用于存储 数组