> 文档中心 > 动态规划的应用

动态规划的应用


1. 硬币支付问题

有1元,5元,10元,50元,100元,500元的硬币各c1,c5,c10,c50,c100,c500枚.

现在要用这些硬币来支付A元,最少需要多少枚硬币?

假定本题至少存在一种支付方案.

0≤ci≤10^9

0≤A≤10^9

输入:

第一行有六个数字,分别代表从小到大6种面值的硬币的个数

第二行为A,代表需支付的A元

样例:

输入

3 2 1 3 0 2
620

输出

6

package 动态规划;import java.util.Arrays;import java.util.Scanner;/** * @author: DreamCode * @file: 硬币支付问题.java * @time: 2022-4-2-20:52:23 * @method: 分别采用基本DFS以及DFS+备忘录进行搜索。这里尝试使用动态规划无果,可能的原因是在自底向上逐步迭代的时候,有些硬币的      数值是无法凑出来的 */public class 硬币支付问题 {static int[] cnts = new int[6];static int[] coins = { 1, 5, 10, 50, 100, 500 };static int[][] rec; // 备忘录递归public static void main(String[] args) {Scanner scanner = new Scanner(System.in);for (int i = 0; i < 6; i++) {cnts[i] = scanner.nextInt();}int A = scanner.nextInt();int ans = DFS(A, 5); // DFS递归rec = new int[A + 1][6];int ans2 = rec_DFS(A, 5); // 备忘录式递归System.out.println(ans);System.out.println(ans2);}private static int rec_DFS(int a, int k) {// TODO 备忘录递归if (a == 0) {return 0;}if (k == 0) {return a;}if (rec[a][k] != 0) {return rec[a][k];}int count = a / coins[k];count = Math.min(count, cnts[k]);int res = count + rec_DFS(a - count * coins[k], k - 1);rec[a][k] = res;return res;}private static int DFS(int a, int k) {// TODO 深搜递归if (k == 0) {return a;}if (a == 0) {return 0;}int count = a / coins[k];count = Math.min(count, cnts[k]);return count + DFS(a - count * coins[k], k - 1);}}

2. 钢条切割问题

Serling公司购买长钢条,将其切割为短钢条出售。切割工序本身没有成本支出。公司管理层希望知道最佳的切割方案。
假定我们知道Serling公司出售一段长为i英寸的钢条的价格为pi(i=1,2,…,单位为美元)。钢条的长度均为整英寸。

长度i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
价格pi | 1 | 5 | 8 | 16 | 10 | 17 | 17 | 20 | 24 | 30 |

钢条切割问题是这样的:给定一段长度为n英寸的钢条和一个价格表pi(i=1,2,…n),求切割钢条方案,使得销售收益rn最大。
注意,如果长度为n英寸的钢条的价格pn足够大,最优解可能就是完全不需要切割。

package 动态规划;/** * @author: DreamCode * @file: 钢条切割问题.java * @time: 2022-4-3-10:18:55 * @method: 递归方法:当前的钢条长度i支持前j种切割方法,别人遍历每一种切割方法,记录最优解; *   动态规划方法:钢条长度为0的时候最优解肯定为0,钢条长度从1到n逐步迭代,对于每次的钢条长度i,找出支持的j种切割方法      种的最优解 */public class 钢条切割问题 {static int[] p = { 1, 5, 8, 16, 10, 17, 17, 20, 24, 30 };static int n = 10;static int[] rec;public static void main(String[] args) {int ans_dfs = DFS(n);  //深搜DFSSystem.out.println(ans_dfs);rec = new int[n + 1];int ans_rec = rec_DFS(n); // 备忘录方法System.out.println(ans_rec);int ans_dp = DP(); // 动态规划算法求解最优解System.out.println(ans_dp);}private static int DP() {// TODO 动态规划算法求解最优解int[] dp = new int[n + 1];dp[0] = 0; // 钢条长度为0时的价值为0for (int i = 1; i <= n; i++) { // 这里的j是p的下标,从0~n-1;但是实际切割长度是1~n;所以这里是j+1代表切割长度for (int j = 0; i >= (j + 1) && j < p.length; j++) { // 当前的钢条长度i支持切割大小为j的长度dp[i] = Math.max(dp[i], dp[i - (j + 1)] + p[j]); // 不切与切,选择最优子问题}}return dp[n];}private static int rec_DFS(int k) {// TODO DFS+备忘录获得最优解if (k == 0) { // 当前钢条长度为0return 0;}if (rec[k] != 0) {return rec[k];}int res = 0;for (int i = 1; i <= p.length; i++) { // 切的长度是1到n,等于n代表整体,不用切if (k >= i) { // 当前的长度支持切res = Math.max(res, p[i - 1] + rec_DFS(k - i));}}rec[k] = res;return res;}private static int DFS(int k) {// TODO DFS深搜遍历获得最优解if (k == 0) { // 当前钢条长度为0return 0;}int res = 0;for (int i = 1; i <= p.length; i++) { // 切的长度是1到n,等于n代表整体,不用切if (k >= i) { // 当前的长度支持切res = Math.max(res, p[i - 1] + DFS(k - i));}}return res;}}

3. 数字三角形

在数字三角形中寻找一条从顶部到底边的路径,使得路径上所经过的数字之和最大。

路径上的每一步都只能往左下或 右下走。只需要求出这个最大和即可,不必给出具体路径。

三角形的行数大于1小于等于100,数字为 0 - 99

输入格式:

5 //表示三角形的行数 接下来输入三角形

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

要求输出最大和

package 动态规划;import java.util.Arrays;import java.util.Scanner;/** * @author: DreamCode * @file: 数字三角形.java * @time: 2022-4-3-14:37:49 * @method: DFS:从顶点逐步往下递归,每次将当前顶点的值加上两条分支中的最大值,当到达最底层时,直接将节点的值返回。 动态规划: */public class 数字三角形 {/** * 在数字三角形中寻找一条从顶部到底边的路径,使得路径上所经过的数字之和最大。
* 路径上的每一步都只能往左下或 右下走。只需要求出这个最大和即可,不必给出具体路径。
* 三角形的行数大于1小于等于100,数字为 0 - 99 输入格式 5 //表示三角形的行数 接下来输入三角形 7 3 8 8 1 0 2 7 4 4 4 * 5 2 6 5 要求输出最大和 * */
static int n;static int[][] rec;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);n = scanner.nextInt();int[][] arr = new int[n][n];rec = new int[n + 1][n + 1];for (int i = 0; i < n; i++) {for (int j = 0; j <= i; j++) {arr[i][j] = scanner.nextInt();}}int ans_dfs = DFS(Arrays.copyOf(arr, n), 0, 0); // DFS方法求最优解int ans_dp = DP(Arrays.copyOf(arr, n)); // 动态规划求解System.out.println(ans_dfs);System.out.println(ans_dp);}private static int DP(int[][] arr) {// TODO 动态规划法求解int[] dp=new int[arr.length];dp = arr[arr.length-1]; //初始化dp数组记录为倒数第一行的值for(int i=arr.length-2;i>=0;i--) { //结合滚动数组,从倒数第二行逐步往上递推for(int j=0;j<=i;j++) {dp[j]=arr[i][j]+Math.max(dp[j], dp[j+1]);}}return dp[0];}private static int DFS(int[][] arr, int x, int y) {// TODO DFS方法求最优解if (x == arr.length - 1) {return arr[x][y];}if (rec[x][y] != 0)return rec[x][y];int res = arr[x][y];res += Math.max(DFS(arr, x + 1, y), DFS(arr, x + 1, y + 1));rec[x][y] = res;return res;}}

4. 完全背包问题

在0-1背包问题的基础上,增加物品数量无限条件; 同时必须理解,抓一个之后用剩余的容量重新考虑当前可选的所有物品其实包含了抓2个甚至更多的情况!!!

package 动态规划;import java.util.Scanner;/** * @author: DreamCode * @file: 完全背包问题.java * @time: 2022-4-3-15:46:27 * @method: DFS:在当前背包容量为i的情况下,当前的物品可选,选择能让价值最大 的数目或者是不选;当前物品不支持选,直接进入下一    层;     动态规划:初始化状态包括只有第一个物品与背包容量为0的情况,逐步递推前i种物品下,背包容量为j的最优子问题。这里在选      与不选第i个物品中取最大值时,因为每个物品有无数个,所以如果当前选择了第i种物品,那么接下来依然有i种物品可选 */public class 完全背包问题 {static int[] values = { 9, 5, 3, 1 };static int[] weights = { 7, 4, 3, 2 };static int n = 4;static int total = 100;static int[][] rec;public static void main(String[] args) {rec = new int[total + 1][n + 1];int ans_dfs = DFS(total, 0);System.out.println(ans_dfs);int ans_dp = DP();System.out.println(ans_dp);}private static int DP() {// TODO 动态规划求最优解int[][] dp = new int[n][total + 1];for (int i = 0; i <= total; i++) { // 初始化第一行,只有一种物品,尽可能多拿就行if (i >= weights[0]) {dp[0][i] = (i / weights[0]) * values[0];} else {dp[0][i] = 0;}}for (int i = 0; i < n; i++) {// 初始化第一列,当所剩空间为0时,没法选任何物品dp[i][0] = 0;}for (int i = 1; i < n; i++) {for (int j = 1; j <= total; j++) {if (j >= weights[i]) { // 当前j空间大小支持选择第i中物品dp[i][j] = Math.max(dp[i][j - weights[i]]+values[i], dp[i - 1][j]); // 选与不选中取最大值,这里因为有无数个物品,所以如果当前选择了第i种物品,那么接下来还是依然有i种物品可选} else {dp[i][j] = dp[i - 1][j];}}}return dp[n-1][total];}private static int DFS(int N, int k) {// TODO DFS求最优解,N为当前背包剩余的容量,k为当前可选的物品if (rec[N][k] != 0)return rec[N][k];if (k == n) {return 0;}int res = 0;for (int i = 0; i <= N / weights[k]; i++) {res = Math.max(i * values[k] + DFS(N - i * weights[k], k + 1), res);}rec[N][k] = res;return res;}}

5. 最大公共子序列

求最大公共子序列问题 AB34C A1BC2 结果为 ABC

package 动态规划;import java.util.ArrayList;import java.util.List;import java.util.Scanner;/** * @author: DreamCode * @file: 最大公共子序列.java * @time: 2022-4-3-15:02:07 * @method:DFS:利用list存储两字符串相同的字符,逐个比较s1与s2的字符,如果当前字符相同,则递归查询字串的最长公共子序列,将公     共子序列的公共字符加入到当前字符list中,总是维护更新一个最长的公共字符list;   动态规划法:当s1[i]==s2[j]时:dp[i][j] = dp[i - 1][j - 1] + 1;否则dp[i][j] = Math.max(dp[i - 1][j], dp[i][j- 1]); */public class 最大公共子序列 {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String s1 = scanner.next();String s2 = scanner.next();String dfs_ans = DFS(s1, s2).toString();System.out.println(dfs_ans);String ans_dp = DP(s1, s2); // 动态规划求解System.out.println(ans_dp);}private static String DP(String s1, String s2) {// TODO 动态规划求解子问题int len1 = s1.length();int len2 = s2.length();int[][] dp = new int[len1][len2];for (int i = 0; i < len1; i++) { // 初始化第一列if (i > 0 && dp[i - 1][0] == 1) {dp[i][0] = 1;} else {if (s1.charAt(i) == s2.charAt(0)) {dp[i][0] = 1;} else {dp[i][0] = 0;}}}for (int i = 0; i < len2; i++) {// 初始化第一行if (i > 0 && dp[0][i - 1] == 1) {dp[0][i] = 1;} else {if (s1.charAt(0) == s2.charAt(i)) {dp[0][i] = 1;} else {dp[0][i] = 0;}}}for (int i = 1; i < len1; i++) {for (int j = 1; j < len2; j++) {if (s1.charAt(i) == s2.charAt(j)) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}return parseString(dp, s1, s2);}private static String parseString(int[][] dp, String s1, String s2) {// TODO 解析出最长公共子序列StringBuilder res = new StringBuilder();int len1 = s1.length() - 1;int len2 = s2.length() - 1;while (len1 > 0 && len2 > 0) {if (dp[len1][len2] > dp[len1 - 1][len2] && dp[len1][len2] > dp[len1][len2 - 1]) {// 比左和上大,一定是当前位置的字符相等res.insert(0, s1.charAt(len1));len1--;len2--;} else if (dp[len1 - 1][len2] >= dp[len1][len2 - 1]) {len1--;} else {len2--;}}if (len1 == 0 && len2 == 0 &&dp[0][0]==1) {res.insert(0, s2.charAt(0));} else if (len2 == 0 && dp[len1][0] == 1) {res.insert(0, s2.charAt(0));} else if (len1 == 0 && dp[0][len2] == 1) {res.insert(0, s1.charAt(0));}return res.toString();}private static List<Character> DFS(String s1, String s2) {// TODO DFS查询最长公共子序列List<Character> ans = new ArrayList<>();for (int i = 0; i < s1.length(); i++) {List<Character> list = new ArrayList<>();for (int j = 0; j < s2.length(); j++) {if (s1.charAt(i) == s2.charAt(j)) { // s1的第i个字符与s2的第j个字符相同,进行递归list.add(s1.charAt(i));list.addAll(DFS(s1.substring(i + 1), s2.substring(j + 1)));break;}}if (list.size() > ans.size()) {ans = list;}}return ans;}}

6. 最长递增子序列的长度

输入 4 2 3 1 5 6 输出 3 (因为 2 3 5组成了最长递增子序列)

package 动态规划;import java.util.Scanner;/** * @author: DreamCode * @file: 最长递增子序列的长度.java * @time: 2022-4-3-19:58:35 * @method: 尺取法遍历,时间复杂度为n^2    动态规划法1:对于第i个字符,在前i-1个最短递增子序列种,当arr[i]>arr[j]时:dp[i]=Math.max(dp[i], dp[j]+1);    否则,arr[i]为前i个数中最小的值,dp[i]=1;    动态规划法2:dp[p]记录的是当前长度p的最长递增子序列的最后一个元素。    对于每一个arr[i],如果arr[i]>dp[p],则dp[p+1]=arr[i];    否则,扫描dp数组,替换第一个比arr[i]大的dp[j]。因为对于递增子序列来说,末尾的数越小,则其能继续递增的机会越大 */public class 最长递增子序列的长度 {static int[] arr = {4, 2, 3, 1, 5, 6, 4, 8, 5, 9};public static void main(String[] args) {int ans = f();System.out.println(ans);int ans_dp=DP();System.out.println(ans_dp);int ans_dp2=DP2();System.out.println(ans_dp2);}private static int DP2() {// TODO 第二种动态规划方法int[] dp = new int[arr.length + 1];    dp[1] = arr[0];//长度为1的最长递增子序列,初始化为第一个元素    int p = 1;//记录dp更新的最后位置    for (int i = 1; i < arr.length; i++) {      if (arr[i] > dp[p]) { dp[p + 1] = arr[i]; p++;      } else { //扫描dp数组,替换第一个比arr[i]大的dp  for (int j = 0; j <= p; j++) {    if (dp[j]>arr[i]){      dp[j]=arr[i];      break;    }  }      }    }   return p;}private static int DP() {// TODO 第一种动态规划法求最优解int len=arr.length;int[] dp=new int[len];dp[0]=1;  //第一个数单独组成一个递增序列for(int i=1;i<len;i++) {for(int j=i-1;j>=0;j--) {if(arr[i]>arr[j]) {dp[i]=Math.max(dp[i], dp[j]+1);}}if(dp[i]==0) {dp[i]=1;}}return dp[len-1];}private static int f() {// TODO 尺取法获取最优解int len=arr.length;int maxCnt=0;for(int i=0;i<len;i++) {int cnt=1;int p=i;for(int j=i+1;j<len;j++) {if(arr[j]>arr[p]) {p=j;cnt++;}}maxCnt=Math.max(cnt, maxCnt);}return maxCnt;}}