解题思路
-
问题分析:
- 需要从数组中选择一些数,使其和为 的倍数且最大
- 可以转化为求模运算的动态规划问题
- 对于每个数,可以选择或不选择
-
动态规划设计:
- 状态定义: 表示考虑前 个数,和除以 余 时的最大值
- 状态转移:
- 不选第 个数:
- 选第 个数:
- 最终答案:,如果为 则说明无解
-
实现要点:
- 注意处理余数为负数的情况
- 使用 防止溢出
- 初始化时要设置为负无穷,避免无解情况的干扰
代码
#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()
算法及复杂度
- 算法:动态规划
- 时间复杂度:,其中 是数组长度, 是给定的除数
- 空间复杂度:,用于存储 数组