当前位置：文档之家 › 山东科技大学算法设计总文档

山东科技大学算法设计总文档

  • 格式：doc
  • 大小：643.00 KB
  • 文档页数：19

下载文档原格式

  / 19

合集下载

山东科技大学(研究生院)

山东科技大学(研究生院)
山东科技大学（研究生院）
学院：交通学院 班级：2017
专业：交通信息工程及控制、交通运输规划与管理
课程表3月5日起执行
课 星
程 期
节次
一
二
三
四
五
六
日
上
午
1
2
工程结构计算分析（9-16）
纪巧玲
翻译基础（跨文化交际）崔倩1（1-18）
工程结构计算分析（9-16）
纪巧玲
教室
J9-224
J5-303
J9-224
车辆智能控制理论及应用（1-8）
韩以伦
汽车数字化设计与制造（9-16）
王树凤
车辆系统动力学
（1-8）
李旭
汽车安全技术（9-16）
韩善灵
教室
J5-412
J5-412
J5-303
J5-412
J5-412
3
4
机电系统分析与设计（1-8）
王素玉
有限元方法及应用（9-16）
薛风先
创新研究（1-9）
王素玉
中国特色社会主义理论邵勇2（10-18）
曹冲振
教室
J5-311
J5-412/ J5-202
J9-109
3
4
现代物流建模理论及算法设计
（9-16）
孙慧
物流装备自动化技术（2-9）
曹冲振
现代物流建模理论及算法设计（10-17）
孙慧
高级管理学
（9-16）
宋作玲
现代设计理论与方法（1-8）
韩善灵
教室
J9-226
J9-109/J9-226
J5-412
山东科技大学（研究生院）
学院：交通学院 班级：2017

山东大学算法分析与设计重点PPT文档共26页

山东大学算法分析与设计重点PPT文档共26页

山东大学算法分析与设计重点
6、法律的基础有两个，而且只有两个……公平和实用。——伯克 7、有两种和平的暴的法律才有好的秩序。——亚里士多德 9、上帝把法律和公平凑合在一起，可是人类却把它拆开。——查·科尔顿 10、一切法律都是无用的，因为好人用不着它们，而坏人又不会因为它们而变得规矩起来。——德谟耶克斯
谢谢
11、越是没有本领的就越加自命不凡。——邓拓 12、越是无能的人，越喜欢挑剔别人的错儿。——爱尔兰 13、知人者智，自知者明。胜人者有力，自胜者强。——老子 14、意志坚强的人能把世界放在手中像泥块一样任意揉捏。——歌德 15、最具挑战性的挑战莫过于提升自我。——迈克尔·F·斯特利

2022年山东科技大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年山东科技大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年山东科技大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。

A.插入B.选择C.希尔D.二路归并2、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。

A.NB.2N-1C.2ND.N-13、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表4、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。

A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改5、已知串S='aaab'，其next数组值为（）。

A.0123B.1123C.1231D.12116、下列选项中，不能构成折半查找中关键字比较序列的是（）。

A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4507、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（）。

A．只有e B．有e、b C．有e、c D．无法确定8、一个具有1025个结点的二叉树的高h为（）。

A.11B.10C.11至1025之间D.10至1024之间9、有n（n>0）个分支结点的满二叉树的深度是（）。

A.n2-1B.log2（n+1）+1C.log2（n+1）D.log2（n-l）10、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（）。

A.(n-1)/2B.n/2C.(n+1)/2D.n二、填空题11、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为______次；当使用监视哨时，若查找失败，则比较关键字的次数为______。

《算法设计综合实验》教案（5篇）

《算法设计综合实验》教案（5篇）

《算法设计综合实验》教案（5篇）第一篇：《算法设计综合实验》教案《算法设计综合实验》教案统计与应用数学学院2012年5月11日制实验一数据类型、运算符和表达式实验目的：1、掌握C语言数据类型，熟悉如何定义一个整型、字符型和实型的变量，以及对它们赋值的方法；2、掌握不同的数据类型之间赋值的规律；3、学会使用C的有关算术运算符，以及包含这些运算符的表达式，特别是自加和自减运算符的使用；4、学会使用赋值运算符及复合赋值运算符；5、进一步熟悉C程序的编辑、编译、连接和运行的过程。

实验环境：Windows操作系统、Visual C++6.0实验学时：2学时；实验内容：1、整型变量实型变量、字符型变量的定义与输出，赋整型常量值时的情形，以及给整型变量赋字符常量值时的情形；2、各类数值型数据间的混合运算；3、要将“China”译成密码，密码规律是：用原来的字母后面第4各字母代替原来的字母。

例如，字母“A”后面第4个字母是“E”，用“E”代替“A”。

因此，“China”应译成“Glmre”。

请编一程序，用赋初值的方法使c1、c2、c3、c4、c5这5个变量的值分别为’C’、’h’、’i’、’n’、’a’，经过运算，使c1、c2、c3、c4、c5分别变为’G’、’l’、’m’、’r’、’e’，并输出。

实验二顺序结构程序设计实验目的：1、掌握C语言中赋值语句的使用方法；2、掌握各种类型数据的输入输出方法，能正确使用各种格式转换符；3、学习调试程序。

实验环境： Windows操作系统、Visual C++6.0 实验学时：2学时；实验内容：1、掌握各种格式转换符的正确使用方法；2、设圆半径r=1.5，圆柱高h=3，求圆周长、圆面积、圆球表面积、圆球体积、圆柱体积。

用scanf输入数据，输出计算结果。

输出时要有文字说明，取小数点后两位数字。

3、编程序：用getchar函数读入两个字符给c1、c2，然后分别用putchar函数和printf函数输出这两个字符。

山东科技大学数据结构与操作系统07-08,2010--2020年考研初试真题

山东科技大学数据结构与操作系统07-08,2010--2020年考研初试真题
四、[15分]采用链表作存储结构，编写一个采用选 择排序方法进行升序排序的函数。
五、[15分]采用二叉链表存储树，试写一算法，实现 对树的层次遍历。
六、[15分]设计一个算法，判断无向图G是否一棵树。
操作系统部分（50分）
一：名词解释（每题3分，总计12分）
1：线程
2：死锁
3：虚拟存储器 4：中断 二：简单题（每题5分，总计20分）
2、[10分]设有一有向图G如下图所示：
1
2
6
5 3
4
(1)、画出图G的邻接表存储表示（邻接顶点请以顶 点序号递增序排列，以使答案唯一）。
(2)、写出从顶点1开始按深度优先遍历G得到的顶 点序列。 3、[10分]已知待排序的三个整数a,b和c(a≠b≠c≠a), 可能出现的六种排列情况的概率不等，其概率如下 表所示：
1、[4分]为什么要分析算法的时间复杂度？ 2、[4分]简述代码区、全局数据区、栈区、堆区
在程序运行时的作用。 3、[4分]求模式串s＝’aaaabc’的next及nextval
函数。 4、[4分]证明根据森林的先序序列与中序序列
可以唯一确定一个森林。 二、综合应用题[每小题8分，共24分]：
1、[8分]推导满k叉树上的叶子结点数n0和非 叶子结点数n1之间的关系（即用k和n1表示n 0）。
下表中等待访问磁盘的序列：
请求序列
1 2 34 5 67 8
将要访问的柱面号 36 192 41 57 121 66 64 100
请按两种磁盘调度算法 SCAN 算法（也称电梯调度算法）和最短寻道时间优先调度算 法，回答以下两个问题：（1）分别给出请求序列的柱面号处理次序；（2）比较两种 算法的优缺点。
A. 4 B. 3 C. 2 D. 1

基于粒子群优化算法的分数阶PID控制器设计

基于粒子群优化算法的分数阶PID控制器设计

基于粒子群优化算法的分数阶PID控制器设计
赵华东;宋保业;张建胜;许琳
【期刊名称】《山东科技大学学报（自然科学版）》
【年(卷),期】2017(036)004
【摘要】分数阶PID控制器具有可变的微分和积分阶次,通过调整控制器参数可以获得更好的控制性能.本文基于粒子群优化算法设计分数阶PID控制器.首先介绍分数阶PID和粒子群优化算法,然后给出分数阶PID控制系统结构、分数阶微积分算子的近似算法和分数阶PID控制器设计的仿真流程,最后通过MATLAB/Simulink 对算例进行控制器设计仿真.仿真结果表明,通过粒子群寻优能够获得满意的分数阶PID控制器参数,满足对控制性能的要求.
【总页数】6页(P60-65)
【作者】赵华东;宋保业;张建胜;许琳
【作者单位】山东科技大学电气与自动化工程学院,山东青岛 266590;山东科技大学电气与自动化工程学院,山东青岛 266590;山东科技大学电气与自动化工程学院,山东青岛 266590;山东科技大学电气与自动化工程学院,山东青岛 266590【正文语种】中文
【中图分类】TP273
【相关文献】
1.分数阶系统的分数阶PID控制器设计 [J], 薛定宇;赵春娜
2.基于粒子群优化算法的分数阶PID控制器设计 [J], 蒋建辉
3.改进的粒子群优化算法优化分数阶PID控制器参数 [J], 金滔;董秀成;李亦宁;任磊;范佩佩
4.基于改进BBO算法的分数阶PID控制器设计 [J], 吴正平; 尹凡; 汪昊
5.基于改进状态空间模型遗传算法的分数阶PID控制器优化设计 [J], 齐战; 李茂军; 肖雨荷; 刘芾
因版权原因，仅展示原文概要，查看原文内容请购买。

算法设计与分析知到章节答案智慧树2023年山东科技大学

算法设计与分析知到章节测试答案智慧树2023年最新山东科技大学第一章测试1.程序运行结果往往与输入相关，所以程序可以不满足确定性（）参考答案:错2.有关算法分析的事后统计法正确的是（）。

参考答案:结果是面向机器，面向程序员，面向语言的;测试的结果与程序的编译和运行环境有关;结果与测试的样本数据有关3.下面哪些内容是算法设计之前要完成的内容? ( )参考答案:是求精确解还是近似解;确定合适的数据结构4.函数10logn3+5logn2的渐近表达式为（）：参考答案:O(logn)5.下列函数根据渐近阶从低到高顺序是（）参考答案:logn ＜ n1/2 ＜2n ＜n3 ＜3n ＜n!6.研究NPC 问题的意义: 一旦某个NPC问题找到了多项式时间复杂性的算法，那么所有的NP问题都找到了多项式时间算法。

( )参考答案:对第二章测试1.直接或间接的调用自身的算法称为（）。

参考答案:递归算法2.Hanoi塔问题如下图所示。

现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。

移动圆盘时遵守Hanoi塔问题的移动规则。

由此设计出解Hanoi塔问题的递归算法正确的为：（）参考答案:3.分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题分别解决子问题最后将子问题的解组合起来形成原问题的解。

这要求原问题和子问题（）。

参考答案:问题规模不同，问题性质相同4.利用二分搜索，最坏情况下的计算时间复杂性为（）。

参考答案:O (logn)5.二分搜索算法只适用（）存储结构。

参考答案:顺序6.使用二分搜索算法在1000个有序元素表中搜索一个特定元素，在最坏情况下，搜索总共需要比较的次数为（）。

参考答案:107.线性时间选择的时间复杂度为（）。

参考答案:O(n)8.利用合并排序，其辅助空间为（）：参考答案:O（n）9.利用快速排序，对数的序列{16, 27, 13, 2, 15,38}，选择基准16，进行一次划分，结果为（）：参考答案:{13, 2, 15} 16 {27, 38}10.分治策略解决棋盘覆盖问题是一个渐近意义下最优的算法.（）参考答案:对第三章测试1.设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ，若xm=yn则（）。

山东科技大学2018年算法设计与分析考试题真题【范本模板】


｝
………………………………………………………………【3分】
3。 template<class Type〉 int Search（Type a[］,int
n)
｛ Int l=0； int r=n-1； while （r >= l){
int m = （l+r）
/if2(;m = = a[m］） return mif (;m< a[m]） r = m—1； else l = m+1；
物品 A B C D E F G 重量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30
一、简答题（1题4分，2题4分，3题6分，共14分）
1.算法是指解决问题的一种方法或一个过程。………………………………………【2分】 程序是算法用某种程序设计语言的具体实现………………………………………【2分】
（1）O（g（n）) = { f（n） ｜存在正常数 c和 n0使得对所有 n n0有：0 f(n) cg（n) ｝ ,记 为 f（n） ＝ （O2)（g（ （ng)(） n)），或= 说｛ f（fn（）n)|的 存阶在不 正高常于 数cg和（nn0） 使的得阶对当所有n n n0时有。：…0……cg…(n…)记…为……f（…n…）【3分】 f＝(n） ｝(，g（n）），或说 f(n）的阶不低于 g(n)的阶当 n 时。…………………………【3分】
四、对于动态规划算法，试解答：（1题4分，2题6分，3题10分，共20分）
1.动态规划算法的两个基本要素，每个要素的含义是什么?
2。写出动态规划算法解题的基本步骤。 3。 0－1背包问题：给定 n个物品和一个背包。物品 i的重量为 wi，价值为 vi，背包容量为 c。问如何选择装入 背包中的物品，使得装入背包的物品的价值最大？在装入背包时，每种物品 i只有两种选择，装入或者不装入，既 不能装入多次，也不能只装入一部分。

山东科技大学计算机图形学实验指导书

计算机图形学实验指导书张晓庆信息科学与工程学院2010年5月目录实验一环境设置（2学时）实验二直线和圆的生成算法（2学时）实验三填充和裁剪算法（4学时）实验四（选择1）二维图形的几何变换（2学时）实验四（选择2）真实感图形的绘制（2学时）实验一环境设置（2学时）一、实验目的1．掌握图形驱动程序及图形模式的基本概念，掌握图形初始化方法；2．掌握Turbo C 进行图形程序设计的基本方法；3．了解Turbo C 的图形功能，了解常见的图形库函数；4．初步了解OpenGL程序设计结构；了解OpenGL的基本数据类型、核心函数及辅助函数的使用。

二、实验要求1．图形系统初始化；2．综合应用Turbo C 中图形库函数，进行图形设计与绘制；3．熟悉Turbo C 和OpenGL开发环境，要求会对程序进行编辑，编译，调试（包括分步，断点设置等调试手段）。

三、实验内容1．图形系统初始化#include <graphics.h>include <stalib.h>include <stdio.h>include <conio.h>int main(void){int gdriver=DETECT,gmode=0;initgraph(&gdiver,&gmode,”C:\\BC31\\BGI”);//进行图形初始化，//图形卡的采用自动检//测模式，同时//假设BC系统安装在C盘的BC31子目//录下。

setcolor(4); //设定当前前景色为红色circle(300,300,100); //以点（300，300）为圆心，100为半径画//圆周。

setcolor(2); //设定当前前景色为绿色line(100,100,100,600); //在点(100,100)和点（100,600）之间画一条//直线段，并和以下三句结合，画出长为//500宽为400的矩形。

山东省考研计算机学科复习资料算法设计与分析重要知识点总结

山东省考研计算机学科复习资料算法设计与分析重要知识点总结算法设计与分析是计算机学科考研中的重要内容之一，对于考生来说，掌握算法设计与分析的重要知识点是提高考试成绩的关键之一。

本文将针对山东省考研计算机学科复习资料，总结算法设计与分析的重要知识点，帮助考生更好地备考。

下面将从基本概念、常见算法、算法效率分析等方面进行详细总结。

一、基本概念1. 算法定义：算法是解决特定问题的一系列有限步骤的描述，通过这一系列步骤可以将输入转化为输出。

2. 算法的特性：算法应具备明确性、有限性、输入输出、实用性、确定性和可行性。

3. 算法描述方法：算法可以用自然语言、伪代码和流程图等方式进行描述。

二、常见算法1. 排序算法排序算法是算法设计与分析中的基础内容，常见的排序算法包括冒泡排序、插入排序、选择排序、快速排序、归并排序等。

这些算法在实际应用中都有各自的优点和缺点，考生需要掌握它们的原理、思想以及实现方式。

2. 查找算法查找算法是在一组数据中寻找特定元素的算法，常见的查找算法包括顺序查找、二分查找和哈希查找。

不同的算法适用于不同的数据结构和问题场景，考生需要了解它们的特点和适用范围。

3. 图算法图算法涉及到图的遍历、最短路径、最小生成树等问题，常见的图算法包括深度优先搜索、广度优先搜索、Dijkstra算法和Prim算法等。

图算法在网络、社交网络等领域有广泛的应用，考生需要掌握它们的基本原理和实现方式。

三、算法效率分析算法效率分析是算法设计与分析中的重要内容，考生需要了解常用的算法复杂度分析方法，包括时间复杂度和空间复杂度。

1. 时间复杂度时间复杂度是衡量算法运行时间与输入规模之间关系的指标，常见的时间复杂度有常数阶、对数阶、线性阶、平方阶、指数阶等。

考生需要学会通过代码分析和数学计算等方法来确定算法的时间复杂度。

2. 空间复杂度空间复杂度是衡量算法所需的额外空间与输入规模之间关系的指标，常见的空间复杂度有常数阶、线性阶、对数阶、平方阶等。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

《算法设计与分析》实验报告班级计算机2011-3班姓名学号2013年12 月08 日目录实验一二分查找程序实现…………………………………………………………………01页实验二棋盘覆盖问题………………………………………………………………………04页实验三0-1背包问题的动态规划算法设计……………………………………………….07页实验四背包问题的贪心算法………………………………………………………………10页实验五最小重量机器设计问题（回溯法） (12)页实验六最小重量机器设计问题（分支限界法） (15)页指导教师对实验报告的评语成绩：指导教师签字：年月日算法分析与设计实验报告—二分搜索算法的实现一、实验目的建立算法复杂度的理论分析与实验分析的联系，深刻体会算法复杂度作为算法的好坏评价指标的本质含义。

二、实验要求1、用c/c++语言实现二分搜索算法。

2、通过随机产生有序递增数组的方法，测出二分查找算法平均意义下比较次数随问题规模的变化结果，并绘制曲线表示。

三、实验原理折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。

它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。

如果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。

如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。

二分搜索法的应用极其广泛，而且它的思想易于理解。

四、实验过程(步骤)1、产生随机有序递增数组使用rand（）函数产生随机数，并组织成有序数组, ; 为使每次产生的随机数不同使用随机数发生器的初始化函数srand(time(0))for ( int j=100; j <=1000; j+=100 ) {array[0]=10+rand()%15;for(int i=1; i<j; i++) {// 生成递增随机数列array[i]=array[i-1]+1+rand()%3+rand()%10;}产生要查找的数的下标suffix 为要搜索的元素下标int suffix = rand() % j;key 为要查找的数据int key = array[suffix];2、统计理论平均查找次数和实际平均查找次数float count=0.0 //平均实际查找次数根据二分查找的算法可得理论平均查找次数为O（log n）；3、二分查找int BinarySearch( int b[], int key, int left, int right ) {while( left <= right ) {middle = ( left + right ) / 2;if (Key == b[middle]) {RowCount++;return middle;}else if ( key < b[middle] ) {right = middle - 1;RowCount++;}else {left = middle + 1;RowCount++;}}return -1; //没有找到}五、运行结果x:数组个数y:平均查找时间系列1：理论平均查找时间系列2：实际平均查找时间六、实验分析与讨论在试验中，遇到了如何产生随机数递增数组的问题，解决方法是采用rand（）函数获得随机递增数组和要查找的数字下标。

采用随机化的数组，能够更加具有普遍性，更加能够证明算法的平均查找时间。

七、实验心得二分查找在搜索有序表时，效率比较高。

通过这次实验我对二分查找算法的认识又有了新的提高。

指导教师对实验报告的评语成绩：指导教师签字：年月日算法分析与设计实验报告—分治法解决棋盘覆盖问题一、实验目的建立算法复杂度的理论分析与实验分析的联系，深刻体会算法复杂度作为算法的好坏评价指标的本质含义。

二、实验要求1、用c++程序语言实现分治法解决棋盘覆盖问题。

2、分析算法的时间复杂度三、实验原理用分治策略，可以设计解决棋盘问题的一个简介算法。

当k>0时，可以将2^k *2^k棋盘分割为4个2^k-1 * 2^k-1子棋盘。

由棋盘覆盖问题得知，特殊方格必位于4个较小的子棋盘中，其余3个子棋盘中无特殊方格。

为了将3个无特殊方格的子棋盘转化为特殊棋盘可以将一个L型骨牌覆盖这3个较小棋盘的会合处，所以，这3个子棋盘上被L型覆盖的方格就成为给棋盘上的特殊方格，从而将原问题转化为4个较小规模的棋盘覆盖问题。

递归的使用这种分割，直至棋盘简化为1*1棋盘为止。

四、实验过程(步骤)1、数据说明：tr：棋盘上左上角方格的行号tc：棋盘上左上角方格的列号dr：特殊方格所在的行号dc：特殊方格所在的列号定义了全局变量tile，用于进行覆盖。

区分4种不同L类型的骨牌，初始值为0.Board[]数组用来表示棋盘2、函数说明ChessBoard函数实现了递归的将棋盘划分为子棋盘，并将棋盘进行覆盖。

main()函数用来进行输入棋盘的大小和特殊棋盘的位置。

使用memset(Board,0,sizeof(Board))将Board[]数组清零使用setw()函数控制输出格式五、运行结果六、实验分析与讨论设T（n）是算法ChessBoard覆盖一个2^k * 2^k棋盘所需要的时间，则从算法的分治策略可知，T(k)满足如下递归方程：O（1）k = 0T(k) = {4T(k-1)+O（1）k>0解得此递归方程可得T(k) = O（4^k）。

由于覆盖一个2^k *2^k棋盘所需的L型骨牌个数为（4^k —1）/3,故算法ChessBoard是一个在渐进意义下最优的算法七、实验心得通过这次试验，更多的了解了分治法解题的思路就是将大问题化为若干子问题，再依次解决子问题，最后获得问题的答案。

是我更加熟练地使用分治策略解决问题。

指导教师对实验报告的评语成绩：指导教师签字：年月日算法分析与设计实验报告——0-1背包问题的动态规划算法的实现一、实验目的建立算法复杂度的理论分析与实验分析的联系，深刻体会算法复杂度作为算法的好坏评价指标的本质含义。

二、实验要求1、用c++语言实现0-1背包问题的动态规划算法。

2、分析0—1背包问题动态规划算法的时间复杂度并提出优化建议。

三、实验原理动态规划算法的基本思想是将待求解的问题分解成若干相关不独立的子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

用一个表存储已解决的子问题的答案，不管该问题是否被用到，只要被计算过，就存入表中。

这样我们就可以在多项式时间内在表中找到需要的已求得的答案，避免了大量的重复计算。

这就是动态规划算法的基本思想。

四、实验过程(步骤)1、最优解结构分析及递归式由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。

设所给0-1背包问题的子问题的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。

由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。

此时背包容量为j，可选择物品为i。

此时在对xi作出决策之后,问题处于两种状态之一:(1)背包剩余容量是j,没产生任何效益；(2)剩余容量j-wi,效益值增长了vi ；2、数据说明：N：物品个数C：背包容量W[]:物品重量数组V[]:物品价值数组3、函数说明void Knapsack(int *v,int *w,int c,int n, int m[][C+1]) 计算所给出的0-1背包问题的最优解void Traceback(int m[][C+1],int *w,int c,int n,int *x)根据函数Knapsack（）计算出的m[][]数组计算出最优解，并输出结果。

int min(int x,int y)比较大小并返回较小的值；int maxint x,int y)比较大小并返回较大的值；五、运行结果六、实验分析与讨论按上述算法Krapsack计算后，m[1][c]所给出要求的0-1背包问题的最优值。

相应的最优解可有函数Tracback（）根据m[][]数组计算得出。

计算复杂性分析：从计算m（i，j）的递归式看出，函数Knapsack需要O(nc)计算出时间，函数Traceback 需要O（n）计算时间。

算法Knapsack有两个较明显的缺点。

其一是算法要求所给的物品的重量必须是整数，其次，当背包容量c很大时，算法需要的计算时间较多。

当c>2^n时，算法Knapsack需要Ω（n2^n）计算时间。

七、实验心得使用动态规划算法用于解0-1背包问题，比穷举法具有相当好的效率。

由于0-1背包的时间复杂度为O(2^n),所以是一个NP难问题，可以通过计算跳跃点的方式转变为计算复杂度为多项式时间内的算法，从而对算法进行了优化。

这次实验用到的是动态规划法，0-1背包问题用动态规划法首先要构造动态规划表，用三个for语句实现；根据动态规划表每行的最大值变化确定每个元素的装入与否，逐步确定出装入背包的物品，背包容量的最大值也就是动态规划表最右下角。

通过这次试验更加熟悉了动态规划算法的原理以及使用。

指导教师对实验报告的评语成绩：指导教师签字：年月日算法分析与设计实验报告——背包问题的贪心算法的实现一、实验目的建立算法复杂度的理论分析与实验分析的联系，深刻体会算法复杂度作为算法的好坏评价指标的本质含义。

二、实验要求1、用c++语言实现背包问题的贪心算法。

2、分析算法的计算复杂性并验证能否得到最优解三、实验原理贪心算法总是做出在当前看来是最好的选择。

贪心算法并不从整体最优上加以考虑，它总是做出的选择只是在某种意义上的局部最优选择。

贪心法解决背包问题的基本步骤：首先计算每种物品单位重量的价值v/w，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。

若将这种物品全部装入背包后，背包内的物品总重量未超过才，则选择单位重量价值次高的物品并尽可能多的装入背包。

以此策略一直进行下去，直到背包装满为止。

五、实验过程(步骤)数据说明：N：物品数量c:背包容量V[]:物品价值数组m[]:物品重量数组x[]:物品放入背包的重量函数说明：V oid Knapsack(int n,float c,float w[],float x[]) 用来计算最大价值Sort（int n,float v[],float w[]）用来计算单位重量价值的物品，并从大到小进行排序。

五、运行结果七、实验分析与讨论Knapsack算法的主要计算时间在于将个物品依其单位重量的价值从大到小排序。