欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

dynamic programming 部分问题

程序员文章站 2024-03-23 23:24:58
...

 

dynamic programming 部分问题

 

Code：

递归版本：

import java.util.Scanner;

public class z1 {

	static int n;

	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		n = input.nextInt(); // 输入硬币的数量
		int[] coins = new int[n + 1];
		coins[0] = 0;
		for (int i = 1; i <= n; i++) { // 硬币从下标为1开始，直到 n
			coins[i] = input.nextInt();
		}
		System.out.println(solve(coins, 1)); // 解决

	}

	// 递归有两种情况， 选和不选当前的位置
	public static long solve(int[] coins, int sign) {
		// 位置合法的情况下
		if (sign >= 1 && sign <= n) {
			// 选择当前位置，然后判断相邻一个硬币的可能性， 不选择当前位置，递归判断相邻两个硬币的情况（选or不选）
			return Math.max(coins[sign] + solve(coins, sign + 2), solve(coins, sign + 1));
		}
		return 0;
	}

}

 

动态规划：

package dynamic_2019_02_18;

import java.util.Scanner;

public class z1_1 {

	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int n = input.nextInt(); // 输入硬币的数量

		int[] coins = new int[n + 1];

		for (int i = 1; i <= n; i++) { // 硬币从下标为1开始，直到 n
			coins[i] = input.nextInt();
		}

		System.out.println(solve(coins, n));

	}

	// 递归改成了动态规划两种情况， 选和不选当前的位置
	public static int solve(int[] coins, int n) {
		int[][] value = new int[n][n + 2];
		for (int i = 1; i < n; i++) {
			for (int j = 1; j <= n; j++) {
				if (j == n) { // 最后硬币（边界情况），选择，不选
					value[i][j] = Math.max(coins[j] + value[i - 1][j - 2], value[i - 1][j - 1]);
				} else if (j == 1) {
					value[i][j] = coins[j];
				} else {
					value[i][j] = Math.max(coins[j] + value[i - 1][j - 2], value[i - 1][j - 1]);
				}

			}
		}

		int maxValue = 0;
		for (int i = 0; i <= n + 1; i++) {
			maxValue = Math.max(maxValue, value[n - 1][i]);
		}
		return maxValue;

	}

	// 动态规划 优化
	public int getMaxGold(int w[], int n) {
		int f[][] = new int[n + 1][2];
		f[0][0] = 0; // 当前位置不选择的最大值
		f[0][1] = w[0]; // 当前位置选择的最大值
		for (int i = 1; i < n; ++i) {
			f[i][0] = Math.max(f[i - 1][0], f[i - 1][1]);
			f[i][1] = f[i - 1][0] + w[i];
		}
		return Math.max(f[n - 1][0], f[n - 1][1]);
	}

}

 

dynamic programming 部分问题

 

递归版本：

package dynamic_2019_02_18;

import java.util.Scanner;

public class z2 {

	/*
	 * 题目是这个样子的 年份T 工作的数量M 可以更换工作的次数S 工资的二维数组salary[M + 1][T + 1]
	 */
	static int T, M, S;

	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		T = input.nextInt(); // 输入年数
		M = input.nextInt(); // 输入工作的数量
		S = input.nextInt(); // 输入可以更换工作的次数

		int[][] salary = new int[M + 1][T + 1]; // 工作对应年份的工资
		for (int i = 1; i <= M; i++) {
			for (int j = 1; j <= T; j++) {
				salary[i][j] = input.nextInt(); // 工作i 在第j年的工资
			}
		}
		long maxSalary = 0;
		for (int i = 1; i <= M; i++) { // 第一年选择的工作
			maxSalary = Math.max(maxSalary, salary[i][1] + solve(salary, i, 2, 0));
		}

		System.err.println("获得的最大工资是：" + maxSalary);
	}

	// 工资数组、选择的工作 s、当前年份 t、更换工作的次数
	public static long solve(int[][] salary, int s, int t, int num) {
		long maxNum = 0;
		if (t <= T) {

			// 不更换工作
			if (num <= S) { // 无法在更换工作或不更换的情况下，继续当前的工作获得的工资
				maxNum = salary[s][t] + solve(salary, s, t + 1, num);
			}
			if (num < S) {
				long tmpSalary = 0; // 更换工作 获得的最大工资
				for (int i = 1; i <= M; i++) {
					if (i != s) {
						tmpSalary = Math.max(tmpSalary, salary[i][t] + solve(salary, i, t + 1, num + 1));
					}
				}
				// 不更换工作和更换工作获得的最大工资
				maxNum = Math.max(tmpSalary, maxNum);
			}
			return maxNum;
		}
		return maxNum;

	}

}

 

动态规划：

package dynamic_2019_02_18;

import java.util.Scanner;

public class z2_2 {

	/*
	 * 题目是这个样子的 年份T 工作的数量M 可以更换工作的次数S 工资的二维数组salary[T][M]
	 */
	static int T, M, S;

	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		T = input.nextInt(); // 输入年数
		M = input.nextInt(); // 输入工作的数量
		S = input.nextInt(); // 输入可以更换工作的次数

		int[][] salary = new int[T][M]; // 工作对应年份的工资
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < T; j++) {
				salary[i][j] = input.nextInt(); // 工作i 在第j年的工资
			}
		}

		System.err.println("获得的最大工资是：" + solve(salary, T, M, S));
	}

	// 工作数组（某年，某职业的工资）、 T年、 m 职业、 S更换工作次数
	public static int solve(int salary[][], int T, int M, int S) {
		int f[][][] = new int[T][M][S + 1]; // 存储某年某职业更换工作次数的最大工资
		int g[][] = new int[T][S + 1]; // 某年里，更换了多少次工作的最大工资

		// 第1年，所有职业的最高工资等于当前的工资
		for (int j = 0; j < M; j++) {
			f[0][j][0] = salary[j][0];
			g[0][0] = Math.max(g[0][0], f[0][j][0]);
		}

		for (int i = 1; i < T; i++) { // 寻找i年中得最高的工资
			for (int j = 0; j < M; j++) { // 职业j的最大工资情况
				for (int k = 0; k <= i && k <= S; k++) { // 更换工作次数 （一年换一次，而且有最大换工作的次数的限制）
					f[i][j][k] = Math.max(f[i][j][k], f[i - 1][j][k] + salary[i][j]); // 不更换工作的情况
					if (k >= 1) {
						f[i][j][k] = Math.max(f[i][j][k], g[i - 1][k - 1] + salary[i][j]); // 更换工作的情况，（存在覆盖）保留最大的
					}
				}
			}

			// 一年结束，结算工资，（某职业，换工作次数的最大工资）
			for (int j = 0; j < M; j++) {
				for (int k = 0; k <= S; ++k) {
					g[i][k] = Math.max(g[i][k], f[i][j][k]);
				}
			}
		}
		int ans = 0;
		for (int j = 0; j < M; j++) {
			for (int k = 0; k <= S; k++) {
				ans = Math.max(ans, f[T - 1][j][k]); // 找出最后一年的最大的工资（最后一年的所有职业中）
//				ans = Math.max(ans, g[j][k]); // 等价于这个
			}
		}
		return ans;
	}

}

 

dynamic programming 部分问题

dynamic programming 部分问题

 

该题目的欧洲版本的递归改成动态规划自己没有思路，博客记录

 

递归版本：

package dynamic_2019_02_18;

import java.util.Scanner;

public class z3_3 {

	static int n;

	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		n = input.nextInt();
		// 输入游戏的参数 n * n的地图
		int[][] map = new int[n + 1][n + 1];
		boolean[][] flag = new boolean[n + 1][n + 1];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				map[i][j] = input.nextInt();
				flag[i][j] = false;
			}
		}

		long AmericanMaxSum = Long.MIN_VALUE;
		long EuropeanManSum = Long.MIN_VALUE;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				AmericanMaxSum = Math.max(AmericanMaxSum, AmericanSolve(map, i, j));
				EuropeanManSum = Math.max(EuropeanManSum, EuropeanSolve(map, flag, i, j));
			}
		}
		System.out.println("AmericanMaxSum = " + AmericanMaxSum);
		System.out.println("EuropeanManSum = " + EuropeanManSum);

	}

	// 美国的只能选择一个位置，然后选择下面或者右边
	public static long AmericanSolve(int[][] map, int i, int j) {
		// 如果范围合法的话、选择当前位置，同时选择向下走或者向右走最大的一步
		if (1 <= i && i <= n && 1 <= j && j <= n) {
			return map[i][j] + Math.max(AmericanSolve(map, i + 1, j), AmericanSolve(map, i, j + 1));
		}
		return 0;
	}

	// 欧洲版本的可以选择下面、左边、右边、但是不能重复选取
	public static long EuropeanSolve(int[][] map, boolean[][] flag, int i, int j) {
		// 如果范围合法的话、且没有走过的话、选择当前位置，同时选择向下、向左、向右走最大的一步
		if (1 <= i && i <= n && 1 <= j && j <= n && !flag[i][j]) {
			flag[i][j] = true;
			long down = map[i][j] + EuropeanSolve(map, flag, i + 1, j);
			long left = map[i][j] + EuropeanSolve(map, flag, i, j - 1);
			long right = map[i][j] + EuropeanSolve(map, flag, i, j + 1);
			flag[i][j] = false;
			return Math.max(down, Math.max(left, right));
		}

		return 0;
	}
}

 

动态规划：

package dynamic_2019_02_18;

import java.util.Scanner;

public class z3 {

	static int n;
	static int value[][], value1[][]; // 美国玩法、欧洲玩法

	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		n = input.nextInt();
		// 输入游戏的参数 n * n的地图
		int[][] map = new int[n + 1][n + 1];
		boolean[][] flag = new boolean[n + 1][n + 1];
		value = new int[n + 1][n + 1]; // 美国玩法的记录
		value1 = new int[n + 1][n + 1]; // 欧洲玩法的记录 // 没有思路。 递归怎么修改

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				map[i][j] = input.nextInt();
				flag[i][j] = false;
			}
		}

		System.out.println("美国玩法的值是：" + AmericanSolve(map));

		long EuropeanManSum = Long.MIN_VALUE;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				EuropeanManSum = Math.max(EuropeanManSum, EuropeanSolve(map, flag, i, j));
			}
		}
		System.out.println("欧洲玩法的值是：" + EuropeanManSum);

	}

	// 美国的当前位置，只能从左边或者上面来到 、 如果都是负值（左边、上面）的话，我就不选择
	public static int AmericanSolve(int[][] map) {
		value[1][1] = map[1][1];
		for (int i = 2; i <= n; i++) { // 对第1行第i列的数据进行处理、 只能从上面来
			value[1][i] = map[1][i] + Math.max(0, value[1][i - 1]);
		}
		for (int i = 2; i <= n; i++) { // 对第i行第1列的数据进行处理，只能从左边来
			value[i][1] = map[i][1] + Math.max(0, value[i - 1][1]);
		}

		// 其余情况 当前的元素 可以来至左边，或者上面， 选择最大的一个
		for (int i = 2; i <= n; i++) {
			for (int j = 2; j <= n; j++) {
				int tmp = Math.max(value[i - 1][j], value[i][j - 1]);
				value[i][j] = map[i][j] + Math.max(0, tmp); // 上面，左边的值和0那个大，选择最大的
			}
		}

		int maxValue = Integer.MIN_VALUE;
		for (int i = 1; i <= n; i++) {
			maxValue = Math.max(maxValue, Math.max(value[n][i], value[i][n]));
		}
		return maxValue;
	}

	// 欧洲版本的可以选择下面、左边、右边、但是不能重复选取
	public static long EuropeanSolve(int[][] map, boolean[][] flag, int i, int j) {
		// 如果范围合法的话、且没有走过的话、选择当前位置，同时选择向下、向左、向右走最大的一步
		if (1 <= i && i <= n && 1 <= j && j <= n && !flag[i][j]) {
			flag[i][j] = true;
			long down = map[i][j] + EuropeanSolve(map, flag, i + 1, j);
			long left = map[i][j] + EuropeanSolve(map, flag, i, j - 1);
			long right = map[i][j] + EuropeanSolve(map, flag, i, j + 1);
			flag[i][j] = false;
			return Math.max(down, Math.max(left, right));
		}

		return 0;
	}
}

 

别人的代码，自己没有思路，记录下来

dynamic programming 部分问题

dynamic programming 部分问题

上一篇： SpringBoot解读启动类内容（第三天）

下一篇： springBoot 入门（三）—— 使用 RestController

推荐阅读