动态规划解决最长子序列问题+背包问题实验报告
需积分: 5 153 浏览量
2023-05-06
21:03:48
上传
评论
收藏 307KB DOC 举报
实验一：动态规划
一、实验目的
1、理解动态规划的基本思想，理解动态规划算法的两个基本要素最优子结构性质和子问题
的重叠性质。
2、熟练掌握典型的动态规划问题。
3、掌握动态规划思想分析问题的一般方法，对较简单的问题能正确分析，设计出动态规划
算法，并能快速编程实现。
二、实验内容
1.最长公共子序列问题
（1）问题描述
若给定序列 X={x
1
,x
2
,…,x
m
}，则另一序列 Z={z
1
,z
2
,…,z
k
}是 X 的子序列，是指存在一
个严格递增下标序列{i
1
,i
2
,…,i
k
}使得对于所有 j=1,2,…,k 有：z
j
=x
ij
。例如，序列 Z={B，
C，D，B}是序列 X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，
7}。给定 2 个序列 X 和 Y，当另一序列 Z 既是 X 的子序列又是 Y 的子序列时，称 Z 是序列 X
和 Y 的公共子序列。给定 2 个序列 X={x
1
,x
2
,…,x
m
}和 Y={y
1
,y
2
,…,y
n
}，找出 X 和 Y 的最长
公共子序列。
（2）实验代码
#include<stdio.h>
#include<string.h>
int c[200][200]; //用 c[i][j]记录 X[i]与 Y[j] 的 LCS 的长度
int b[200][200]; //b[i][j]记录 c[i][j]是通过哪一个子问题的值求得的，以决定
搜索的方向
char f[200];
/*取 c[i-1][j]和 c[i][j-1]的最大值,并记录 c[i][j]是通过哪一个子问题的值求得
的，以决定搜索的方向*/
int Max(int m,int n,int i,int j)
{
if(m > n)
{
b[i][j] = -1;
return m;
}
资源评论
搬砖杂记
- 粉丝: 57
- 资源: 13
最新资源
- 论文(最终)_20240430235101.pdf
- 基于python编写的Keras深度学习框架开发，利用卷积神经网络CNN,快速识别图片并进行分类
- 最全空间计量实证方法（空间杜宾模型和检验以及结果解释文档）.txt
- 5uonly.apk
- 蓝桥杯Python组的历年真题
- 2023-04-06-项目笔记 - 第一百十九阶段 - 4.4.2.117全局变量的作用域-117 -2024.04.30
- 2023-04-06-项目笔记 - 第一百十九阶段 - 4.4.2.117全局变量的作用域-117 -2024.04.30
- 前端开发技术实验报告：内含4四实验&实验报告
- Highlight Plus v20.0.1
- 林周瑜-论文.docx
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
