grant's Blog

记录生活中的点点滴滴

算法基础课笔记（二三）

发表于 更新于 分类于 ，   阅读次数： Valine：
本文字数： 7.1k 阅读时长 ≈ 6 分钟

四：动态规划

DP问题没有代码模板。

4.1：背包问题

关于本章的所有背包问题请参考《DP背包问题详解》，这里不再赘述。

背包问题是常见的DP模型。

这里直接放出代码。

例题：2. 01背包问题（模板题）

朴素写法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String[] str1 = reader.readLine().split(" ");
		int n = Integer.parseInt(str1[0]);
		int m = Integer.parseInt(str1[1]);
		int[][] dp = new int[n+1][m+1];
		
		int v,w;
		for (int i = 1;i <= n;i ++){
		    String[] str2 = reader.readLine().split(" ");
			v = Integer.parseInt(str2[0]);
			w = Integer.parseInt(str2[1]);
			
			for (int j = 0;j <= m;j ++){
			    dp[i][j] = dp[i-1][j];// 也可以写Math.max(dp[i][j],xxx)
				if (j >= v) dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-v] + w);
			}
		}
		reader.close();
		System.out.println(dp[n][m]);
	}
}

滚动数组空间优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String[] str1 = reader.readLine().split(" ");
		int n = Integer.parseInt(str1[0]);
		int m = Integer.parseInt(str1[1]);
		int[] dp = new int[m+1];
		
		int v,w;
		for (int i = 1;i <= n;i ++){
		    String[] str2 = reader.readLine().split(" ");
			v = Integer.parseInt(str2[0]);
			w = Integer.parseInt(str2[1]);
			
			for (int j = m;j >= v;j --){
				dp[j] = Math.max(dp[j], dp[j-v] + w);
			}
		}
		reader.close();
		System.out.println(dp[m]);
	}
}

例题：3. 完全背包问题（模板题）

朴素写法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String[] str1 = reader.readLine().split(" ");
		int n = Integer.parseInt(str1[0]);
		int m = Integer.parseInt(str1[1]);
		int[][] dp = new int[n+1][m+1];
		
		int v,w;
		for (int i = 1;i <= n;i ++){
			String[] str2 = reader.readLine().split(" ");
			v = Integer.parseInt(str2[0]);
			w = Integer.parseInt(str2[1]);
			for (int j = 0;j <= m;j ++){
				for (int k = 0;k*v <= j;k ++){
					dp[i][j] = Math.max(dp[i][j], dp[i-1][j-k*v] + k*w);
				}
			}
		}
        reader.close();
		System.out.println(dp[n][m]);
	}
}

状态转移方程时间优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String[] str1 = reader.readLine().split(" ");
		int n = Integer.parseInt(str1[0]);
		int m = Integer.parseInt(str1[1]);
		int[][] dp = new int[n+1][m+1];
		
		int v,w;
		for (int i = 1;i <= n;i ++){
			String[] str2 = reader.readLine().split(" ");
			v = Integer.parseInt(str2[0]);
			w = Integer.parseInt(str2[1]);
			for (int j = 0;j <= m;j ++){
			    dp[i][j] = dp[i-1][j];
			    if (j >= v)
				    dp[i][j] = Math.max(dp[i][j], dp[i][j-v] + w);
			}
		}
        reader.close();
		System.out.println(dp[n][m]);
	}
}

滚动数组空间优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String[] str1 = reader.readLine().split(" ");
		int n = Integer.parseInt(str1[0]);
		int m = Integer.parseInt(str1[1]);
		int[] dp = new int[m+1];
		
		int v,w;
		for (int i = 1;i <= n;i ++){
			String[] str2 = reader.readLine().split(" ");
			v = Integer.parseInt(str2[0]);
			w = Integer.parseInt(str2[1]);
			for (int j = v;j <= m;j ++){
				    dp[j] = Math.max(dp[j], dp[j-v] + w);
			}
		}
        reader.close();
		System.out.println(dp[m]);
	}
}

例题：4. 多重背包问题 I（模板题）

朴素写法。（和完全背包的朴素写法很像，多了物品数量限制）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String[] str1 = reader.readLine().split(" ");
		int n = Integer.parseInt(str1[0]);
		int m = Integer.parseInt(str1[1]);
		int[][] dp = new int[n+1][m+1];
		
		int v,w,s;
		for (int i = 1;i <= n;i ++){
			String[] str2 = reader.readLine().split(" ");
			v = Integer.parseInt(str2[0]);
			w = Integer.parseInt(str2[1]);
			s = Integer.parseInt(str2[2]); 
			for (int j = 0;j <= m;j ++){
				for (int k = 0;k*v <= j && k <= s;k ++){
					dp[i][j] = Math.max(dp[i][j], dp[i-1][j-k*v] + k*w);
				}
			}
		}
        reader.close();
		System.out.println(dp[n][m]);
	}
}

例题：5. 多重背包问题 II（模板题）

二进制时间优化，滚动数组空间优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.io.*;
public class Main {
	static final int  N = 12000;// 分组N的上限是n*logS == 1000*log2000
	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String[] str1 = reader.readLine().split(" ");
		int n = Integer.parseInt(str1[0]);
		int m = Integer.parseInt(str1[1]);
		int[] dp = new int[m+1];
		int[] v = new int[N];
		int[] w = new int[N];
		
		int cnt = 0;
		int a,b,s;// 通过倍增思想重新分组，小组数量由n*S缩减到n*logS
		for (int i = 1;i <= n;i ++){
			String[] str2 = reader.readLine().split(" ");
			a = Integer.parseInt(str2[0]);
			b = Integer.parseInt(str2[1]);
			s = Integer.parseInt(str2[2]);
			
			int k = 1;
			while (k <= s){
			    cnt ++;
				v[cnt] = a*k;
				w[cnt] = b*k;
				s -= k;k *= 2;
			}
			if (s > 0){
			    cnt ++;
				v[cnt] = a*s;
				w[cnt] = b*s;
			}
		}
		
		n = cnt;
		for (int i = 1;i <= n;i ++){
			for (int j = m;j >= v[i];j --){
				dp[j] = Math.max(dp[j], dp[j-v[i]] + w[i]);
			}
		}
        reader.close();
		System.out.println(dp[m]);
	}
}

例题：9. 分组背包问题（模板题）

朴素写法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.io.*;
public class Main {
	static final int N = 105;
	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String[] str1 = reader.readLine().split(" ");
		int n = Integer.parseInt(str1[0]);
		int m = Integer.parseInt(str1[1]);
		int[][] v = new int[N][N];
		int[][] w = new int[N][N];
		int[] s= new int[N];
		int[][] dp = new int[N][N];

		for (int i = 1;i <= n;i ++){
			s[i] = Integer.parseInt(reader.readLine());
			for (int j = 0;j < s[i];j ++){
				String[] str2 = reader.readLine().split(" ");
				v[i][j] = Integer.parseInt(str2[0]);
				w[i][j] = Integer.parseInt(str2[1]);
			}
		}
		
		for (int i = 1;i <= n;i ++){
			for (int j = 0;j <= m;j ++){
			    dp[i][j] = dp[i-1][j]; // 不选这组物品
				for (int k = 0;k < s[i];k ++){ // 选这组物品中的一个
					if (j >= v[i][k])
						dp[i][j] = Math.max(dp[i][j], dp[i-1][j-v[i][k]] + w[i][k]);
				}
			}
		}
        reader.close();
		System.out.println(dp[n][m]);
	}
}

滚动数组空间优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.io.*;
public class Main {
	static final int N = 105;
	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String[] str1 = reader.readLine().split(" ");
		int n = Integer.parseInt(str1[0]);
		int m = Integer.parseInt(str1[1]);
		int[][] v = new int[N][N];
		int[][] w = new int[N][N];
		int[] s= new int[N];
		int[] dp = new int[N];

		for (int i = 1;i <= n;i ++){
			s[i] = Integer.parseInt(reader.readLine());
			for (int j = 0;j < s[i];j ++){
				String[] str2 = reader.readLine().split(" ");
				v[i][j] = Integer.parseInt(str2[0]);
				w[i][j] = Integer.parseInt(str2[1]);
			}
		}
		
		for (int i = 1;i <= n;i ++){
			for (int j = m;j >= 0;j --){
				for (int k = 0;k < s[i];k ++){
					if (j >= v[i][k])
						dp[j] = Math.max(dp[j], dp[j-v[i][k]] + w[i][k]);
				}
			}
		}
        reader.close();
		System.out.println(dp[m]);
	}
}
坚持原创技术分享，您的支持将鼓励我继续创作！