分析
本题的话是组合问题,我们可以采用DP来进行解决。
闫式DP分析法:
下方DP的时间复杂度:10万 * 3 * 1000大概4个亿,会超时。
for (int i = 0; i < N; i ++) //遍历i个数
for (int j = 0; j < 3; j ++) //前i个选择j个
for (int k = 0; k < K; k ++) //前i个选择j个的和 mod K 的目标余数为k
dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - 1][((k - a[i] % K) + K) % K] + a[i]);
正常DP流程会超时,需要进行优化。
接着我们来使用贪心进行优化,我们是否可以从i个数中去筛选出来一部分的数字呢?
- 由于我们在求
dp[i][j][k]
目标过程中,实际上是来使用k-a[i] % K来进行操作的,实际上对于10万个数,每个数% K得到的值一定会是在[0, K - 1]范围中,可能同一个余数对应好几个数,那么我们是否可以找到对应%k中,例如5 % 2 = 1,9%2 = 1,我们只拿到对应最大的三个数,这样即可将原本10万个数直接筛选为3*1000 = 3000个数。
通过贪心优化的时间复杂度:筛选+排序(约15 * 10万)也就是150万再加上dp(3000*3*1000
)900万实际上最终合起来为1000万运行量,可以AC。
实际上对于dp[i][j][k]
还可以进行状态压缩转为二维, 不过对于这种转二维情况需要在内循环中进行逆序遍历。
- 针对于01背包状态压缩内层循环逆序原因:01背包状态压缩内层循环逆序原因(图文并茂,通俗易懂)
题解1:01背包问题,三维解法(贪心优化)
复杂度分析:时间复杂度O(n.k);空间复杂度O(n.k)
//dp+贪心
import java.util.*;
import java.io.*;
class Main {
static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
static int n, K;
//DP数组
static int[][][] fn = new int[3010][4][1010];
//存储余数为[0, K - 1]的数,对应数组下标为余数值
static ArrayList<Integer>[] nums = new ArrayList[1010];
//存储筛选过后的
static int[] a = new int[3010];
static int p;
public static void main(String[] args) throws Exception{
String[] ss = cin.readLine().split(" ");
n = Integer.parseInt(ss[0]);
K = Integer.parseInt(ss[1]);
//初始化集合
for (int i = 0;i < K; i ++) {
nums[i] = new ArrayList<Integer>();
}
//遍历所有的数来存储到对应下标为余数的集合中
ss = cin.readLine().split(" ");
for (int i = 0; i < n; i ++) {
int num = Integer.parseInt(ss[i]);
nums[num % K].add(num);
}
//对所有余数情况的集合来进行排序,每个集合取前3个
p = 1;
for (int i = 0; i < K; i ++) {
ArrayList<Integer> res = nums[i];
//从大到小排序
Collections.sort(res, (o1, o2) -> o2 - o1);
//System.out.println(res);
for (int j = 0; j < 3 && res.size() > j; j ++) {
a[p++] = res.get(j);
}
}
//dp数组初始化
//全部赋初值
for (int i = 0; i < p; i ++) {
for (int j = 0; j < 4; j ++) {
Arrays.fill(fn[i][j], Integer.MIN_VALUE);
}
}
for (int i = 0; i < p; i ++) {
fn[i][0][0] = 0;
}
//DP
for (int i = 1; i < p; i ++) //筛选过后的数
for (int j = 1; j <= 3; j ++) //选择j个数 01背包循环要逆序
for (int k = 0; k < K; k ++) {
fn[i][j][k] = Math.max(fn[i - 1][j][k], fn[i - 1][j - 1][(k - a[i] % K + K) % K] + a[i]);
}
System.out.println(fn[p - 1][3][0]);
}
}
题解2:题解1基础上三维转二维
复杂度分析:时间复杂度O(n.k);空间复杂度O(k)
//dp+贪心
import java.util.*;
import java.io.*;
class Main {
static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
static int n, K;
//DP数组
static int[][] fn = new int[4][1010];
//存储余数为[0, K - 1]的数,对应数组下标为余数值
static ArrayList<Integer>[] nums = new ArrayList[1010];
//存储筛选过后的
static int[] a = new int[3010];
static int p;
public static void main(String[] args) throws Exception{
String[] ss = cin.readLine().split(" ");
n = Integer.parseInt(ss[0]);
K = Integer.parseInt(ss[1]);
//初始化集合
for (int i = 0;i < K; i ++) {
nums[i] = new ArrayList<Integer>();
}
//遍历所有的数来存储到对应下标为余数的集合中
ss = cin.readLine().split(" ");
for (int i = 0; i < n; i ++) {
int num = Integer.parseInt(ss[i]);
nums[num % K].add(num);
}
//对所有余数情况的集合来进行排序,每个集合取前3个
for (int i = 0; i < K; i ++) {
ArrayList<Integer> res = nums[i];
//从大到小排序
Collections.sort(res, (o1, o2) -> o2 - o1);
//System.out.println(res);
for (int j = 0; j < 3 && res.size() > j; j ++) {
a[p++] = res.get(j);
}
}
//System.out.println(Arrays.toString(a));
//dp数组初始化
for (int i = 0; i < 4; i ++)
Arrays.fill(fn[i], Integer.MIN_VALUE);
fn[0][0] = 0;
//DP
for (int i = 0; i < p; i ++) //筛选过后的数
for (int j = 3; j >= 1; j --) //选择j个数
for (int k = 0; k < K; k ++) //余数为k
fn[j][k] = Math.max(fn[j][k], fn[j - 1][(k - a[i] % K + K) % K] + a[i]);
System.out.println(fn[3][0]);
}
}
Orz
题目的分析不要只是截屏,建议思考过后自己画一遍,加深理解。
是滴,确实自己画一遍理解更加透彻