Open Judge——动态规划练习

刺骨的言语ヽ痛彻心扉 2023-09-27 22:44 103阅读 0赞

**目录**

了解动态规划

2760:数字三角形

1、题目

2、代码

4120:硬币

1、题目

2、代码

--------------------

## 了解动态规划 ##

**动态规划** 是编程解题的一种重要手段。1951 年美国数学家 R.Bellman 等人，根据一类多阶段问题的特点，把多阶段决策问题变换为一系列互相联系的单阶段问题，然后逐个加以解决。与此同时，他提出了解决这类问题的“最优化原理”，从而创建了解决最优化问题的一种新方法：动态规划。

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。

我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

动态规划的基本概念：

*  阶段：把所给问题的求解过程恰当地分成若干个相互联系的阶段，以便于求解。过程不同，阶段数就可能不同。描述阶段的变量称为阶段变量，常用 k 表示。阶段的划分，一般是根据时间和空间的自然特征来划分，但要便于把问题的过程转化为多阶段决策的过程。
 *  状态：状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。通常一个阶段有若干个状态，状态通常可以用一个或一组数来描述，称为状态变量。
 *  决策：表示当过程处于某一阶段的某个状态时，可以做出不同的决定，从而确定下一阶段的状态，这种决定称为决策。不同的决策对应着不同的数值，描述决策的变量称决策变量。
 *  状态转移方程：动态规划中本阶段的状态往往是上一阶段的状态和上一阶段的决策的结果，由第 i 段的状态 f(i) ,和决策 u(i) 来确定第 i+1段的状态。状态转移表示为 F(i+1) = T(f(i),u(i))，称为状态转移方程。
 *  策略：各个阶段决策确定后，整个问题的决策序列就构成了一个策略，对每个实际问题，可供选择的策略有一定范围，称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。

动态规划必须满足最优化原理与无后效性。

*  最优化原理：“一个过程的最优决策具有这样的性质：即无论其初始状态和初始决策如何，其今后诸策略对以第一个决策所形成的状态作为初始状态的过程而言，必须构成最优策略”。也就是说一个最优策略的子策略，也是最优的。
 *  无后效性：如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各个状态的影响。

## 2760:数字三角形 ##

[OpenJudge - 2760:数字三角形][OpenJudge - 2760]

#### 1、题目 ####

![9298dba614eb43c494bf9e91ea5a8ddc.png][]

图1给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。  
  
注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。

输入

输入的是一行是一个整数N (1 < N <= 100)，给出三角形的行数。下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。

输出

输出最大的和。

样例输入

5
    7
    3 8
    8 1 0 
    2 7 4 4
    4 5 2 6 5

样例输出

#### 2、代码 ####

import java.util.Scanner;
    
    public class Main {
        static final int MAX_num=100;
        static int[][] d=new int[MAX_num+10][MAX_num+10];
        static int[][] maxS=new int[MAX_num+10][MAX_num+10];
        static int N;
        public static void main(String[] args) {
            int m;
            Scanner sc=new Scanner(System.in);
            N=sc.nextInt();
            for (int i=1;i<=N;i++){
                for (int j=1;j<=i;j++){
                    d[i][j]=sc.nextInt();
                }
            }
            if (N >= 0) System.arraycopy(d[N], 1, maxS[N], 1, N);
            for (int i=N;i>1;i--){
                for (int j=1;j<i;j++){
                    maxS[i-1][j]=Math.max(maxS[i][j+1],maxS[i][j])+d[i-1][j];
    
                }
            }
            System.out.println(maxS[1][1]);
        }
    }

## 4120:硬币 ##

[OpenJudge - 4120:硬币][OpenJudge - 4120]

#### 1、题目 ####

描述

宇航员Bob有一天来到火星上，他有收集硬币的习惯。于是他将火星上所有面值的硬币都收集起来了，一共有n种，每种只有一个：面值分别为a1,a2… an。 Bob在机场看到了一个特别喜欢的礼物，想买来送给朋友Alice，这个礼物的价格是X元。Bob很想知道为了买这个礼物他的哪些硬币是必须被使用的，即Bob必须放弃收集好的哪些硬币种类。飞机场不提供找零，只接受恰好X元。

输入

第一行包含两个正整数n和x。（1 <= n <= 200, 1 <= x <= 10000)  
第二行从小到大为n个正整数a1, a2, a3 … an （1 <= ai <= 10000)

输出

第一行是一个整数，即有多少种硬币是必须被使用的。  
第二行是这些必须使用的硬币的面值（从小到大排列）。

样例输入

5 18
    1 2 3 5 10

样例输出

2
    5 10

提示

输入数据将保证给定面值的硬币中至少有一种组合能恰好能够支付X元。  
如果不存在必须被使用的硬币，则第一行输出0，第二行输出空行。

#### 2、代码 ####

import java.util.Arrays;
    import java.util.Scanner;
    
    public class Main {
    	static int[] dp = new int[1000005];// 表示形成i钱数的方案
    	static int[] ans = new int[1000005];// 表示没有j时形成i钱数的方案数，如果方案数>0.那说明j不必要
    	static int[] a = new int[220];// 存放钱的种类
    	static int[] b = new int[220];// 存放必须有的钱币的种类
    
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		int n, m;// 钱的种类数和礼物价格
    		int count, k;
    		String[] temp;
    		while (sc.hasNext()) {
    			temp = sc.nextLine().split(" ");
    			n = Integer.parseInt(temp[0]);
    			m = Integer.parseInt(temp[1]);
    			temp = sc.nextLine().split(" ");
    			for (int i = 1; i <= n; i++) {
    				a[i] = Integer.parseInt(temp[i-1]);
    			}
    			Arrays.fill(dp, 0, dp.length, 0);
    			dp[0] = 1;// 0元礼物的方案数为1
    			for (int i = 1; i <= n; i++) {
    				for (int j = m; j >= a[i]; j--)// 逆序，典型的0-1背包
    				{
    					dp[j] = dp[j] + dp[j - a[i]];
    					// j是由a[i]和j-a[i]的和，a[i]的方案为1，
    					// j-a[i]的方案数为dp[j-a[i]]；
    				}
    			}
    			count = 0;
    			for (int i = 1; i <= n; i++) {
    				for (int j = 0; j <= m; j++) {
    					if (j < a[i])
    						ans[j] = dp[j];
    					else
    						ans[j] = dp[j] - ans[j - a[i]];
    				}
    				if (ans[m] == 0)// 缺了j就不行了，那么j是必需的
    				{
    					b[count++] = a[i];
    				}
    			}
    			System.out.printf("%d\n", count);
    			if (count == 0)
    				System.out.printf("\n\n");
    			else {
    				for (int i = 0; i < count; i++) {
    					if (i != count - 1)
    						System.out.printf("%d ", b[i]);
    					else
    						System.out.printf("%d\n", b[i]);
    				}
    			}
    
    		}
    	}
    }

[OpenJudge - 2760]: http://bailian.openjudge.cn/practice/2760/
[9298dba614eb43c494bf9e91ea5a8ddc.png]: https://img-blog.csdnimg.cn/9298dba614eb43c494bf9e91ea5a8ddc.png
[OpenJudge - 4120]: http://bailian.openjudge.cn/practice/4120/