【算法设计与分析】动态规划:数塔问题

这篇具有很好参考价值的文章主要介绍了【算法设计与分析】动态规划:数塔问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


题目要求

提示:头歌 算法作业 实验七 动态规划 第1关:数塔问题

本关任务:编写用动态规划解决数塔问题。
【算法设计与分析】动态规划:数塔问题


一、解题关键要点(头歌题目已经给)

【算法设计与分析】动态规划:数塔问题

【算法设计与分析】动态规划:数塔问题

二、解题过程

1.关于数塔问题的动态规划过程自分析【重点】

求解过程(自底向上)

【算法设计与分析】动态规划:数塔问题

决策结果输出过程(自顶向下)

将上述分析求解过程角标记录为path数组 ,方便顺序输出结果

2.解题代码

代码如下(不知题目给出三维数组的a的第三维我用处,去除):

#include <stdio.h> 
#define N 5 //问题规模
int main() {
	int a[50][50];
	a[1][1] = 9;
	a[2][1] = 12, a[2][2] = 15;
	a[3][1] = 10, a[3][2] = 6, a[3][3] = 8;
	a[4][1] = 2, a[4][2] = 18, a[4][3] = 9, a[4][4] = 5;
	a[5][1] = 19, a[5][2] = 7, a[5][3] = 10, a[5][4] = 4, a[5][5] = 16;

	int i, j, dp[50][50] = { 0 }, path[50][50] = { 0 };
	for (j = 1; j <= N; j++)                           //初始子问题 ,倒数第二层(第i-1层)开始
		dp[N][j] = a[N][j];
	for (i = N - 1; i >= 1; i--)                       //进行第 i+1 层的决策,从i 到 1 向上
		for (j = 1; j <= i+1; j++) {                     //每一层有 i+1 个
			if (dp[i + 1][j] > dp[i + 1][j + 1]) {
				dp[i][j] = a[i][j] + dp[i + 1][j];
				path[i][j] = j;                        //本次决策选择下标j的元素
			}
			else {
				dp[i][j] = a[i][j] + dp[i + 1][j + 1];
				path[i][j] = j + 1;                     //本次决策选择下标j+1的元素
			}
		}
	printf("max=%d\n", dp[1][1]);
	printf("数值和最大的路径是:");            
	j = path[1][1];                          //计算dp[1][1]的选择
	for (i = 1; i < N; i++)
	{
		printf("%d->", a[i][j]);
		j = path[i][j];                         //计算dp[i][j]的选择
	}
	printf("%d\n", a[i][j]);
	
}

3.运行结果

【算法设计与分析】动态规划:数塔问题


总结

上课没好好听这块😶‍🌫️,到做题了,瞎揣一气,望指正😢文章来源地址https://www.toymoban.com/news/detail-513395.html

到了这里,关于【算法设计与分析】动态规划:数塔问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 资源分配问题【算法设计与分析】<动态规划问题>

    问题分析: ( 要把问题分为多步解决,每步求出子问题的多个最优策略后一步依赖于上一步的最有策略,最后一步得出问题的解) (1)首先要考虑分配给项目A的资金与利润的关系。得到此时投资数x与其相对应的 的关系。 (2)其次要考虑分配给前两个项目A,B的总资金 与利

    2023年04月08日
    浏览(39)
  • 算法分析与设计——动态规划求解01背包问题

    假设有四个物品,如下图,背包总容量为8,求背包装入哪些物品时累计的价值最多。 我们使用动态规划来解决这个问题,首先使用一个表格来模拟整个算法的过程。 表格中的信息表示 指定情况下能产生的最大价值 。例如, (4, 8)表示在背包容量为8的情况下,前四个物品的最

    2024年02月04日
    浏览(70)
  • 算法设计与分析之动态规划问题和具体实例

           动态规划(Dynamic Programming,DP)算法通常用于求解某种具有最优性质的问题。在这类问题中,可能会有许多可行解,每一个解都对应一个值,我们希望找到具有最优值的解。         动态规划算法与分治法类似,其基本思想也是将待求解的问题分解成若干个子问题,先

    2024年01月19日
    浏览(40)
  • 【计算机算法设计与分析】图像压缩问题(C++_动态规划)

    在计算机中常用像素点灰度值序列 { p 1 , p 2 , . . . , p n } { p_1, p_2, ..., p_n } { p 1 ​ , p 2 ​ , ... , p n ​ } 表示图像。其中整数 p i ( 1 ≤ i ≤ n ) p_i(1leq i leq n) p i ​ ( 1 ≤ i ≤ n ) ,表示像素点i的灰度值。通常灰度值的范围是0~255。因此,需要用8位表示一个像素。 图像的变位压

    2024年02月03日
    浏览(49)
  • 算法设计与分析实验二:动态规划法求解TSP问题和01背包问题

    【实验内容】 (1)tsp问题:利用动态规划算法编程求解TSP问题,并进行时间复杂性分析。 输入:n个城市,权值,任选一个城市出发; 输出:以表格形式输出结果,并给出向量解和最短路径长度。 (2)01背包问题:利用动态规划算法编程求解0-1背包问题,并进行时间复杂性分

    2024年02月03日
    浏览(58)
  • 湘潭大学 算法设计与分析实验 回溯 动态规划 贪心 模拟退火解决背包问题

    https://download.csdn.net/download/SQ_ZengYX/88620871 测试用例

    2024年02月02日
    浏览(62)
  • 算法设计与分析实验4 :利用动态规划的方法解决子集等和分割判断问题

    实验4  利用动态规划的方法解决子集等和分割判断问题 一、实验目的 1. 了解动态规划的主要思想。 2. 掌握背包问题解决方法用以解决该问题。 3. 分析核心代码的时间复杂度和空间复杂度。 二、实验内容和要求 题目:给定一个只包含正整数的非空数组。是否可以将这个数组

    2024年04月23日
    浏览(42)
  • 算法分析与设计-数字三角形问题(动态规划)(通俗易懂,附源码和图解,含时间复杂度分析)(c++)

    (一)题目 问题描述 给定一个由 n n n 行数字组成的数字三角形,如图所示。 试设计一个算法,计算从三角形的顶至底的一条路径,使该路径经过的数字总和最大。 算法设计 对于给定的由 n n n 行数字组成的数字三角形,计算从该三角形的顶至底的路径经过的数字和的最大值

    2023年04月10日
    浏览(45)
  • 算法分析与设计--动态规划

    一、动态规划简介 二、动态规划求解步骤 三、动态规划典型应用 数字三角形问题 最大子段和问题 0-1背包问题 四、最长公共子序列问题 动态规划求解 五、总结 算法语言--java语言 动态规划算法通常用于求解具有某种最优性质的问题。动态规划与分治算法类似,其基本思想也

    2024年02月07日
    浏览(71)
  • 算法设计与分析复习--动态规划

    算法设计与分析复习–递归与分治(二) 与分析法类似:将原问题分解为子问题 不同点:不是通过递归的方式,而是自底向上的求解问题 矩阵连乘的次数是左矩阵行列,右矩阵行列取出左右中进行相乘。 由于矩阵乘积需要满足左矩阵列等于右矩阵的行,所以可以用一维数组

    2024年02月04日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包