当前位置：文档之家 › 算法设计与分析报告课程设计报告材料

算法设计与分析报告课程设计报告材料

  • 格式：doc
  • 大小：86.15 KB
  • 文档页数：8

湖南理工学院课程论文
论文题目 0-1背包问题的设计与实现
课程名称数据结构与算法设计
姓名学号
专业班级年级 2014级
学院计算机学院日期 2015年6月25日
课程论文评价标准
目录
1.问题描述 (3)
2.算法设计分析 (3)
3.程序编码与调试分析 (5)
4.测试结果 (7)
5.自学知识 (7)
6.课程设计心得体会 (8)
7.参考文献 (8)
1.问题描述
给定n种物品和一个背包，物品i的重量是w i，其价值为v i，背包容量为C。

在选择装入背包的物品时，对每种物品i只有两种选择：装入背包或不装入背包，即不能将物品i装入背包多次，也不能只装入物品i的一部分。

问：如何选择装入背包的物品，使得装入背包中物品的总价值最大？
2.算法设计与分析
算法分析
在0-1背包问题中，物体被装入一个背包，或者不被装入背包，设x i表示物品i装入背包的情况，则当x i=0时，表示物品i没有被装入背包，x i=1时，表示物品i被装入背包。

假设有五个物品，其重量分别是{2，2，6，5，4}，价值分别是{6，3，5，4，6}，背包的容量为10。

根据动态规划函数，用一个(n+1)×(C+1)的二维表V，V[i][j]表示把前i个物品装入容量为j的背包中获得的最大价值。

按下述方法来划分阶段：第一阶段，只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值；依此类推，直到第n个阶段。

最后，V(n,C)便是在容量为C的背包中装入n个物品时取得的最大价值。

为了确定装入背包的具体物品，从V(n,C)的值向前推，如果V(n,C)>V(n-1, C)，表明第n个物品被装入背包，前n-1个物品被装入容量为C-w
的背包中；
n
否则，第n个物品没有被装入背包，前n-1个物品被装入容量为C的背包中。

依此类推，直到确定第1个物品是否被装入背包中为止。

算法设计
设n个物品的重量存储在数组w[n]中，价值存储在数组v[n]中，背包容量为C，数组V [n+1][C+1]存放迭代结果，其中V[i][j]表示前i个物品装入容量为j的背包中获得的最大价值，数组x[n]存储装入背包的物品，动态规划法求解0/1背包问题的算法如下：
int KnapSack(int n, int w[ ], int v[ ])
{
for (i=0; i<=n; i++) //初始化第0列
V[i][0]=0;
for (j=0; j<=C; j++) //初始化第0行
V[0][j]=0;
for (i=1; i<=n; i++) //计算第i行，进行第i次迭代
for (j=1; j<=C; j++)
if (j<w[i]) V[i][j]=V[i-1][j];
else V[i][j]=max(V[i-1][j], V[i-1][j-w[i]]+v[i]); j=C; //求装入背包的物品
for (i=n; i>0; i--){
if (V[i][j]>V[i-1][j]) {
x[i]=1;
j=j-w[i];
}
else x[i]=0;
}
return V[n][C]; //返回背包取得的最大价值
}
3.程序编码与调试分析
程序编码
#include<stdio.h>
#include<math.h>
int max(int x,int y){
if(x>=y)
return x;
else
return y;
}
int KnapSack(int n,int C,int *w,int *v,int V[][11]) { int i,j,x[i];
for (i=0;i<=n;i++) //初始化第0列
V[i][0]=0;
for (j=0;j<=C;j++) //初始化第0行
V[0][j]=0;
for (i=1;i<=n;i++) //计算第i行，进行第i次迭代
for (j=1;j<=C;j++)
if (j<w[i])
V[i][j]=V[i-1][j];
else
V[i][j]=max(V[i-1][j], V[i-1][j-w[i]]+v[i]);
j=C; //求装入背包的物品
for (i=n; i>0; i--){
if (V[i][j]>V[i-1][j]) {
x[i]=1;
j=j-w[i];
}
else x[i]=0;
}
for(i=0;i<=n;i++)
{for(j=0;j<=C;j++)
printf("%3d ",V[i][j]);
printf("\n");
}
printf("背包取得的最大价值:");
printf("%d",V[n][C]); //返回背包取得的最大价值
}
int main(){
int n=5,C=10,i;
int V[6][11];
int w[6],v[6];
for(i=1;i<6;i++)
scanf("%d",&w[i]);
for(i=1;i<6;i++)
scanf("%d",&v[i]);
KnapSack(5,10,w,v,V);
}
调试分析
以上0-1背包问题的代码的时间复杂度为O(nc).（n表示物品的总数，c为重量限制背包容量），当背包容量c很大时，算法需要的计算时间比较多。

动态规划依赖于上一个或者上一行的解，所以我常在输出子序列的时候出现问题，这源自于对动态规划的知识不是很了解。

4.测试结果
5.自学知识
在这个程序设计中，涉及了动态规划，动态规划是解决多阶段决策问题常用的最优化理论，其基本思想是沿着决策的阶段划分自问题，决策的阶段可以随时间划分，也可以随着问题的转换状态划分。

设计动态规划算法，通常可按照以下几个步骤进行：
（1）找出最优解的性质，并刻画其结构特征。

（2）递归地定义最优解的值。

（3）以自底而上的方式计算出最优值。

（4）根据计算最优值时得到的信息，构造一个最优解。

6.课程设计心得体会
动态规划依赖于上一个或上一行的解，这次实验总是在输出子序列的时候出现问题，本来动态规划的知识没有学好，正好在最后的课程设计选0-1背包问题作为实验对象，完完整整的通过这次设计对0-1背包问题和动态规划都有了很深刻的了解，这有助于以后我们在实际问题中解决一些复杂性较大的问题，提高程序的运行效率。

7.参考文献
[1] 谭浩强等. 《C语言程序社会》，清华大学出版社，2013.
[2] 王晓华等. 《算法的乐趣》，人民邮电出版社， 2015.。

合集下载

算法设计与分析课程报告

算法设计与分析课程报告

算法设计与分析课程报告第一章算法问题求解基础1、算法的概念：算法是指解决问题的一种方法或过程，是由若干条指令组成的有穷序列。

2、算法的特性①有穷性：一个算法必须保证执行有限步之后结束；②确切性：算法的每一步骤必须有确切的定义；③输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；④输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。

没有输出的算法是毫无意义的；⑤可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成3、算法与程序的关系：区别：程序可以不一定满足可终止性。

但算法必须在有限时间内结束；程序可以没有输出,而算法则必须有输出；算法是面向问题求解的过程描述，程序则是算法的实现。

联系：程序是算法用某种程序设计语言的具体实现；程序可以不满足算法的有限性性质。

4、算法描述方式：自然语言，流程图，伪代码，高级语言。

第二章算法分析基础1、算法复杂性分析：算法复杂性的高低体现运行该算法所需计算机资源（时间，空间）的多少。

算法复杂性度量：期望反映算法本身性能，与环境无关。

理论上不能用算法在机器上真正的运行开销作为标准（硬件性能、代码质量影响）。

一般是针对问题选择基本运算和基本存储单位，用算法针对基本运算与基本存储单位的开销作为标准。

算法复杂性C依赖于问题规模N、算法输入I和算法本身A。

即C=F(N, I, A)。

第五章分治法1、递归算法：直接或间接地调用自身的算法。

用函数自身给出定义的函数称为递归函数。

注：边界条件与递归方程是递归函数的二个要素。

实例：①阶乘函数；②Fibonacci数列；③Ackerman函数；④排列问题；⑤整数划分问题；⑥Hanoi塔问题优缺点：①优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。

②缺点：递归算法的运行效率低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。

算法设计与分析的实验报告

算法设计与分析的实验报告

实验一递归与分治策略一、实验目的1．加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；2．提高学生利用课堂所学知识解决实际问题的能力；3．提高学生综合应用所学知识解决实际问题的能力。

二、实验内容1、①设a[0:n-1]是已排好序的数组。

请写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。

当搜索元素在数组中时，i和j相同，均为x在数组中的位置。

②写出三分搜索法的程序。

三、实验要求（1）用分治法求解上面两个问题；（2）再选择自己熟悉的其它方法求解本问题；（3）上机实现所设计的所有算法；四、实验过程设计（算法设计过程）1、已知a[0:n-1]是一个已排好序的数组，可以采用折半查找（二分查找）算法。

如果搜索元素在数组中，则直接返回下表即可；否则比较搜索元素x与通过二分查找所得最终元素的大小，注意边界条件，从而计算出小于x的最大元素的位置i和大于x的最小元素位置j。

2、将n个元素分成大致相同的三部分，取在数组a的左三分之一部分中继续搜索x。

如果x>a[2(n-1)/3]，则只需在数组a的右三分之一部分中继续搜索x。

上述两种情况不成立时，则在数组中间的三分之一部分中继续搜索x。

五、实验结果分析二分搜索法：三分搜索法：时间复杂性：二分搜索每次把搜索区域砍掉一半，很明显时间复杂度为O(log n)。

（n代表集合中元素的个数）三分搜索法：O（3log3n）空间复杂度：O（1）。

六、实验体会本次试验解决了二分查找和三分查找的问题，加深了对分治法的理解，收获很大，同时我也理解到学习算法是一个渐进的过程，算法可能一开始不是很好理解，但是只要多看几遍，只看是不够的还要动手分析一下，这样才能学好算法。

七、附录：（源代码）二分搜索法：#include<iostream.h>#include<stdio.h>int binarySearch(int a[],int x,int n){int left=0;int right=n-1;int i,j;while(left<=right){int middle=(left+right)/2;if(x==a[middle]){i=j=middle;return 1;}if(x>a[middle])left=middle+1;else right=middle-1;}i=right;j=left;return 0;}int main(){ int a[10]={0,1,2,3,4,5,6,7,8,9};int n=10;int x=9;if(binarySearch(a,x,n))cout<<"找到"<<endl;elsecout<<"找不到"<<endl;return 0;}实验二动态规划——求解最优问题一、实验目的1．加深学生对动态规划算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；2．提高学生利用课堂所学知识解决实际问题的能力；3．提高学生综合应用所学知识解决实际问题的能力。

算法课设实验报告(3篇)

算法课设实验报告(3篇)

第1篇一、实验背景与目的随着计算机技术的飞速发展，算法在计算机科学中扮演着至关重要的角色。

为了加深对算法设计与分析的理解，提高实际应用能力，本实验课程设计旨在通过实际操作，让学生掌握算法设计与分析的基本方法，学会运用所学知识解决实际问题。

二、实验内容与步骤本次实验共分为三个部分，分别为排序算法、贪心算法和动态规划算法的设计与实现。

1. 排序算法（1）实验目的：熟悉常见的排序算法，理解其原理，比较其优缺点，并实现至少三种排序算法。

（2）实验内容：- 实现冒泡排序、快速排序和归并排序三种算法。

- 对每种算法进行时间复杂度和空间复杂度的分析。

- 编写测试程序，对算法进行性能测试，比较不同算法的优劣。

（3）实验步骤：- 分析冒泡排序、快速排序和归并排序的原理。

- 编写三种排序算法的代码。

- 分析代码的时间复杂度和空间复杂度。

- 编写测试程序，生成随机测试数据，测试三种算法的性能。

- 比较三种算法的运行时间和内存占用。

2. 贪心算法（1）实验目的：理解贪心算法的基本思想，掌握贪心算法的解题步骤，并实现一个贪心算法问题。

（2）实验内容：- 实现一个贪心算法问题，如活动选择问题。

- 分析贪心算法的正确性，并证明其最优性。

（3）实验步骤：- 分析活动选择问题的贪心策略。

- 编写贪心算法的代码。

- 分析贪心算法的正确性，并证明其最优性。

- 编写测试程序，验证贪心算法的正确性。

3. 动态规划算法（1）实验目的：理解动态规划算法的基本思想，掌握动态规划算法的解题步骤，并实现一个动态规划算法问题。

（2）实验内容：- 实现一个动态规划算法问题，如背包问题。

- 分析动态规划算法的正确性，并证明其最优性。

（3）实验步骤：- 分析背包问题的动态规划策略。

- 编写动态规划算法的代码。

- 分析动态规划算法的正确性，并证明其最优性。

- 编写测试程序，验证动态规划算法的正确性。

三、实验结果与分析1. 排序算法实验结果：- 冒泡排序：时间复杂度O(n^2)，空间复杂度O(1)。

算法设计 课程设计报告

算法设计 课程设计报告

《算法设计与分析》１什么是算法？算法的特征有哪些？根据我自己的理解，算法是解决问题的方法步骤。

比如在解决高数问题的时候，可以分步骤进行解答，在编程的过程算法可以得到最好的体现。

算法是一系列解决问题的清晰指令，因为我最近在考研复习，对于会的题目还有进行多次的巩固，但是一步步的写很浪费时间，所以我只是写出关键指令，比如化简通分，洛必达法则，上下同阶。

这样可以提高效率。

算法的指令也是同样的。

能够对一定规范的输入，在有限时间内获得所要求的输出。

一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

２若给定某一算法，一般如何对其分析与评价？一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。

计算机的资源，最重要的是时间和空间（存储器）资源。

算法的复杂性有时间复杂性和空间复杂性之分。

1.时间复杂性：例1：设一程序段如下（为讨论方便，每行前加一行号）(1) for i:=1 to n do(2) for j:=1 to n do(3) x:=x+1......试问在程序运行中各步执行的次数各为多少？解答：行号次数(频度)(1) n+1(2) n*(n+1)(3) n*n可见，这段程序总的执行次数是：f(n)=2n2+2n+1。

在这里，n可以表示问题的规模，当n趋向无穷大时，如果f(n)的值很小，则算法优。

作为初学者，我们可以用f(n)的数量级O来粗略地判断算法的时间复杂性，如上例中的时间复杂性可粗略地表示为T(n)=O(n2)。

2.空间复杂性:例2:将一一维数组的数据(n个)逆序存放到原数组中,下面是实现该问题的两种算法:算法1:for i:=1 to n dob[i]:=a[n-i+1];for i:=1 to n doa[i]:=b[i];算法2:for i:=1 to n div 2 dobegint:=a[i];a[i]:=a[n-i-1];a[n-i-1]:=tend;算法1的时间复杂度为2n,空间复杂度为2n算法2的时间复杂度为3*n/2,空间复杂度为n+1显然算法2比算法1优，这两种算法的空间复杂度可粗略地表示为S(n)=O(n)3、从下面算法策略中自选一组，结合某具体问题的求解来介绍算法思想，并加以总结、比较：递归与分治、动态规划与贪心法、回溯法与分支限界法动态规划算法类似于分治法，基本思想也是将待求解问题分解成若干个子问题。