Open Judge——动态规划练习

这篇具有很好参考价值的文章主要介绍了Open Judge——动态规划练习。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

了解动态规划

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:数字三角形

1、题目

Open Judge——动态规划练习

图1给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最大的和。

注意:路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。

输入

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

输出

输出最大的和。

样例输入

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

样例输出

30

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:硬币

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,第二行输出空行。文章来源地址https://www.toymoban.com/news/detail-461412.html

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]);
				}
			}

		}
	}
}

到了这里,关于Open Judge——动态规划练习的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【蓝桥杯冲冲冲】动态规划初步[USACO2006 OPEN] 县集市

    [USACO2006 OPEN] 县集市 The County Fair 每年,FJ 都喜欢去参加县集市,集市上有 n n n 个展位,每个摊位 i i i 都会在当天的特定时间 p i p_i p i ​ 发放精美的礼品。FJ 已经听说了这一点,他希望能收集尽可能多的礼品和他的奶牛们一起分享。要想获得摊位 i i i 发放的礼品,FJ 必须确

    2024年01月22日
    浏览(34)
  • 【带你了解动态规划】

    🔥博主:程序员不想YY啊🔥 💫CSDN优质创作者,CSDN实力新星,CSDN博客专家💫 🤗点赞🎈收藏⭐再看💫养成习惯 🌈希望本文对您有所裨益,如有不足之处,欢迎在评论区提出指正,让我们共同学习、交流进步!🌈 动态规划是一种算法思想,主要用于求解具有重叠子问题和

    2024年04月09日
    浏览(55)
  • LeetCode练习八:动态规划下:背包问题

    参考: 【资料】算法通关手册、背包九讲 - 崔添翼 【文章】背包 DP - OI Wiki 【B站视频】代码随想录详解0-1背包    背包问题 :背包问题是线性 DP 问题中一类经典而又特殊的模型。背包问题可以描述为:给定一组物品,每种物品都有自己的重量、价格以及数量。再给定一个

    2024年01月16日
    浏览(58)
  • 【算法设计与分析】动态规划-练习题

    输入一个整数数组 S[n] ,计算其最长递增子序列的长度,及其最长递增子序列。 定义 k ( 1 ≤ k ≤ n ) k (1 ≤ k ≤ n) k ( 1 ≤ k ≤ n ) ,L[k]表示以 S[k] 结尾的递增子序列的最大长度。子问题即为 L[k]。 对于每一个k,我们都遍历前面0~k-1的所有的数,找出最大的L[i],且 S [ k ] L [

    2024年02月03日
    浏览(57)
  • 动态规划(带你了解 原理 实践)

    目录 引言 一、动态规划的基本概念 二、动态规划的应用 1. 背包问题 2. 最短路径问题 3. 0-1背包问题的变种 4. 字符串匹配与编辑距离 5. 金融投资组合优化 6. 生产调度问题 7. 项目管理中的资源分配 三、动态规划算法的优缺点 优点 1 效率高 2 通用性强 缺点: 1 空间复杂度较高

    2024年03月19日
    浏览(48)
  • 算法练习Day30 (Leetcode/Python-动态规划)

    62. Unique Paths There is a robot on an  m x n  grid. The robot is initially located at the  top-left corner  (i.e.,  grid[0][0] ). The robot tries to move to the  bottom-right corner  (i.e.,  grid[m - 1][n - 1] ). The robot can only move either down or right at any point in time. Given the two integers  m  and  n , return  the number of possible

    2024年01月20日
    浏览(41)
  • 了解动态规划算法:原理、实现和优化指南

    动态规划(Dynamic Programming,简称 DP)是一种通过将原问题拆分成子问题并分别求解这些子问题来解决复杂问题的算法思想。 它通常用于求解优化问题,它的核心思想是将原问题分解成一系列的子问题,通过找到子问题之间的递推关系,可以避免重复计算,从而大幅提高计算

    2024年02月11日
    浏览(35)
  • 动态规划-简单了解下什么是期望DP

    首先说明下为啥是简单了解下,因为对于期望DP的问题 ,相较于一般的动态规划问题,可以说期望DP的题目相对较少,并且往往具有一定的难度。这是因为期望DP在解决问题时需要考虑状态的期望值,涉及到概率和随机性的计算,因此可能需要运用更多的数学知识和技巧 ,所

    2024年02月22日
    浏览(36)
  • 【洛谷】数字三角形(动态规划)

    目录 边读边存 优化成一维数组——倒序没用了? 从上往下存,最大值存在最后一行,最后遍历最后一行得到最大值的写法  边读边存,可以有效降低时间复杂度 在上一篇文章(【洛谷】采药(01背包问题))将二维数组优化成一维数组的过程中,内层循环我们是采用倒序的方

    2024年02月16日
    浏览(38)
  • 【题解 | 基础动态规划】:数字三角形

    链接: [USACO1.5] [IOI1994]数字三角形 Number Triangles 观察下面的数字金字塔。 写一个程序来查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。 在上面的样例中,从 7 → 3 → 8 → 7 → 5 7 to 3 to 8 to 7 to 5 7 →

    2024年04月14日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包