算法分析与设计-实验二 动态规划算法设计

发布时间:2021-11-30 04:50:14



文章目录
1、 数字三角问题2、最长公共子序列问题3、日常购物4、台阶问题



一、实验目的:

掌握动态规划算法的基本思想及适用条件,掌握动态规划算法的设计步骤和具体实现。


二、实验所用仪器及环境
Windows 7 以上操作系统,PC机,codeblocks环境


三、实验原理:
算法总体思想:动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时,有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。
动态规划算法设计步骤:
(1)找出最优解的性质,并刻划其结构特征。
(2)递归地定义最优值。
(3)以自底向上的方式计算出最优值。
(4)根据计算最优值时得到的信息,构造最优解。


四、实验内容:


1、 数字三角问题

问题描述:给定一个由n行数字组成的数字三角形,如下图所示
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5


试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。
如上图最大值为30=7+3+8+7+5


#include
#include
using namespace std;
int a[100][100]={0};
int mem[100][100]={0};
int n;
int memd[100][100]={0};
int dp(int p,int q){
if(mem[p][q]!=0){
return mem[p][q];
}
if(p==n)
{
mem[p][q]=a[p][q];
return mem[p][q];
}

if(dp(p+1,q)>=dp(p+1,q+1))
{
memd[p][q]=q;
}else{
memd[p][q]=q+1;
}
mem[p][q]=max(dp(p+1,q),dp(p+1,q+1))+a[p][q];
return mem[p][q];
}


int main()
{

cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>a[i][j];
}
}

//
cout< int qt,pt;
qt=pt=1;
for(int i=1;i<=n;i++)
{
cout< if(i!=n)
{
cout<<"+";
}
pt=memd[i][pt];
}

return 0;
}
//in
//5
//7
//3 8
//8 1 0
//2 7 4 4
//4 5 2 6 5
//out
//30

2、最长公共子序列问题

问题描述:给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X和Y的最长公共子序列。
输入:
第1行:两个子序列的长度,m n
第2行:第1个子序列的各个元素(序列下标从1开始)
第3行:第2个子序列的各个元素(序列下标从1开始)
输出:
最长公共子序列
实例:
输入:
第1行:
4 5 //m和n的值
第2行
abad //输入4个字符,下标从1开始
第3行
baade //输入5个字符,下标从1开始
输出:
Aad


#include
using namespace std;
int recdp[1000][1000]= {0};

char str1[1000];
char str2[1000];

int dp(int i,int j)
{
///让数组头从开始,dp0,与dp,0都代表空串
///base
if(i==0||j==0)return 0;

///rec
if(recdp[i][j]!=0){return recdp[i][j];}

///相同时直接+1
/// 当这里直接使用图中的0为空字符串时,一定记得,str也是从0开始计算的,所以第五个字符应该是str[4]//
if(str1[i-1]==str2[j-1]){
recdp[i][j]=dp(i-1,j-1)+1;
return recdp[i][j];
}
else{
///不同时直接选大的(我也不知道谁大,那就比比吧)(可能,要1,可能要2,****可能都不要)
///不需要两个都不要,两个都不要的话,第一次不要1,第二次不要2就行了,而且也不会,因为两个都不要一定是最小的
///*******不同时不要+1
recdp[i][j]=max(dp(i-1,j),dp(i,j-1));
return recdp[i][j];
}
return 0;
}
int main()
{
//cout << "Hello world!" << endl;
cin>>str1;
cin>>str2;
cout< return 0;


}


///abcde
///ace
///out
//3

3、日常购物

问题描述:小明今天很开心,因为在家买的新房子即将拿到钥匙。新房里面有一间他自己专用的、非常宽敞的房间。让他更高兴的是,他的母亲昨天对他说:“你的房间需要购买什么物品?怎么布置,你说了算,只要他们的价格总和不超过N元钱”。小明今天早上开始预算,但他想买太多的东西,肯定会超过母亲的N元限额。因此,他把对每件物品的渴望程度,分为5等级:用整数1->5表示,第5等表示最想要。他还从互联网上找到了每件商品(所有整数)的价格。他希望在不超过N元(可能等于N元)的情况下,将每件商品的价格与效益度的乘积的总和最大化.
设第j件物品的价格为p[j],重要度为w[j],其选中的k件商品,编号依次为j1,j2,……,jk,则所求的总和为:
p[j1]×w[j1]+p[j2]×w[j2]+ …+p[jk]×w[jk]。
请帮小明设计一个符合要求的购物清单。
其中N=2000,K=6
p[1]=200 w[1]=2
p[2]=300 w[2]=2
p[3]=600 w[3]=1
p[4]=400 w[4]=3
p[5]=1000 w[5]=4
p[6]=800 w[6]=5


#include
#include
using namespace std;
int p[10000]={0};
int w[10000]={0};
int mem[10000]={0};

int dp(int n,int k){
for(int i=0;i {
for(int j=n;j>=p[i];j--)
{
mem[j]=max(mem[j],mem[j-p[i]]+p[i]*w[i]);
}
}
return mem[n];
}
int main()
{
int n,k;
cin>>n>>k;
for(int i=0;i {
cin>>p[i]>>w[i];
}
cout<
return 0;
}
//in
//2000 6
//200 2
//300 2
//600 1
//400 3
//1000 4
//800 5
//out
//8400

4、台阶问题

问题描述:有n级台阶,一个人每次上一级或者两级,问有多少种走完n级台阶的方法。
实际情况:给定一个矩阵m,从左上角开始每次只能向右走或者向下走,最后达到右下角的位置,路径中所有数字累加起来就是路径和,返回所有路径的最小路径和,如果给定的m如下,那么路径1,3,1,0,6,1,0就是最小路径和,返回12.
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0


#include
#include
using namespace std;
int mem[1000]={0};
int dp(int n)
{
if(n==1)
{
return 1;
}
if(n==2)
{

return 2;
}
if(mem[n]!=0)
{
return mem[n];
}

mem[n]=dp(n-1)+dp(n-2);
return mem[n];
}
int main()
{
int n;
cin>>n;
cout< return 0;
}
//in
//12
//233

五、实验结果与分析:
通过运行程序验证程序的正确性,给出程序运行结果,分析程序出现的bug的原因,调试程序过程种出现的错误和解决方法。

相关文档

  • 孩子自律还是磨蹭,取决于父母是否做好这4点
  • 我心目中的儿童博物馆
  • 2020在校大学生寒假社会实践心得
  • 师范大学生实习自我鉴定
  • 通用版办公房屋租赁合同书范本
  • 关于统筹的英语怎么说
  • 输入法的分类
  • 一个人可以注册几个快手号
  • 蚬子是蛤蜊吗?蚬子和文蛤怎样区别
  • 设计模式 - 命令模式(command pattern) 撤销(undo) 详解
  • 财务咨询公司的经营范围主要是什么
  • mysql安装目录的问题
  • UNIX环境高级编程学习总结
  • 办公室副职竞聘演讲稿
  • 中学生社会实践报告表格
  • 课前预习的重要性探讨
  • 当代干饭人是如何减肥的干饭人怎么能吃不胖
  • 高中校团委工作计划
  • Netty核心组件介绍及手写简易版Tomcat
  • 风箱里的老鼠歇后语_风箱里的老鼠打一歇后语
  • 与女生的聊天技巧有哪些
  • MongoDB 3.4 mongodump 和mongorestore 备份和恢复bson数据
  • 工笔画名家作品欣赏
  • 天秤和十二星座的关系
  • ArcGIS Pro加载天地图
  • 学会放弃
  • 简单版画图片素材
  • 小男孩演出表演化妆的图片
  • 新年开场白和结束语
  • STM32芯片超时无应答 无法连接(USB转串口有黄色感叹号)
  • 猜你喜欢

  • 2014公交公司员工思想汇报范文2000字
  • 商务汉语词汇量101-200
  • 学习张丽莉演讲稿范文
  • 关于坚定信念的励志名言
  • 浅议小学数学教学对学生兴趣的培养策略
  • 《都挺好》观后感集锦5篇
  • 简述3032路pcm帧的结构_PCM30/32路系统帧结构
  • 城市工业产业空间布局优化中的企业搬迁问题研究
  • 安徽省肥东磷矿赵亮经销二部企业信息报告-天眼查
  • 药品冷链物流运作规范-编制说明
  • 配套K12重庆市大学城第一中学校高中数学培优补差练*5 理(无答案)
  • 江西奶业可持续发展研究(一)
  • 数字视频传输技术在城市轨道交通中的应用
  • 家庭装修合同书样本
  • 借款合同范本-定期存单质押书
  • 《丑小鸭》读后感200字_读后感作文
  • 杨烁 当“硬汉”遇到“神犬”
  • 湖南省株洲市2018届高三年级教学质量统一检测理综物理部分(word)
  • 2014年职称英语理工类A级考前押题(2)
  • 2012四川省银行从业资格考试个人贷款真题精选2试题及答案
  • SAMSUNG的Minitab教程 6 sigma 西格玛
  • 羽毛球单打怎么站位
  • 机床夹具设计设计指导书
  • 2018年春沪科版八年级物理导学课件10.第十章 知识梳理
  • 初中语文教学中渗透传统文化的措施
  • Hibernate之HQL左关联配置
  • 解决git一直输入用户名和密码的问题
  • 最新幼儿园春学前班数学期末试卷资料
  • 呆中上口里有鸡打一成语
  • 播音创作基础 重点
  • 中班配班个人工作计划
  • 全县夏季消防检查工作方案
  • 三年级上册英语Unit 2 Lesson 2 What's your name
  • 2021年扬州大学兽医学院829生物化学(自)考研强化模拟五套题
  • 成都尚鼎装饰工程有限公司(企业信用报告)- 天眼查
  • 桦南县广成大榛子种植专业合作社企业信用报告-天眼查
  • 2019年秋冀教版八年级上册英语课件:Unit 6 Lesson 31 How Do You Trave(共25张PPT)
  • 小学一年级优等学生期末评语
  • 人教版高中英语必修4 Unit3 单元语法详解:动词-ing形式作表语
  • A practical study on the implementation of fuzzy logic controllers
  • 企业标准化管理体系建设
  • 气象仪表项目建设申请
  • 电脑版