湖南理工学院课程论文
论文题目 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背包问题的算法如下：intKnapSack(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 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 #include intmax(intx,int y){ if(x>=y) return x; else return y; } intKnapSack(intn,intC,int *w,int *v,int V[][11]) { inti,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 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]); //返回背包取得的最大价值 } intmain(){ int n=5,C=10,i; intV[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. 《土木工程施工课程设计》 课程设计报告 系别：城市建设学院 专业班级：工程管理0802 学生姓名：董小勇 指导教师：贺瑶瑶 （课程设计时间：2011年1月3日——2011年1月17 日）华中科技大学武昌分校 目录 一、课程设计目的 (2) 二、课程设计题目描述和要求 (2) 1、课程设计题目描述 (2) 2、课程设计要求 (2) 三、设计报告内容 (2) 1.工程概况 (2) 1.1建筑设计特点 (2) 1.2结构设计特点 (2) 1.3建筑地点特征 (2) 1.4施工条件 (3) 2.施工方案 (3) 2.1土石方工程 (3) 2.2基础工程 (3) 2.3砌筑工程 (4) 2.4钢筋混凝土工程 (4) 2.5垂直运输和水平运输 (7) 2.6屋面工程 (7) 2.7装饰工程 (7) 2.8板的吊装 (8) 3.施工进度计划 (8) 3.1施工进度计划的作用 (8) 3.2编制依据 (8) 4.施工准备工作计划 (9) 4.1技术资料准备 (9) 4.2物资准备 (9) 4.3劳动组织准备 (10) 4.4施工现场准备 (10) 4.5冬期、雨季施工的准备 (11) 5.劳动力、材料、机械等各项资源需要量计划 (12) 6.施工总平面图的设计步骤 (13) 6.1场外交通的引入 (13) 6.2仓库与材料堆场的布置 (13) 6.3加工厂布置 (13) 6.4布置内部运输道路 (13) 6.5临时水电管网及其他动力设施的布置 (14) 7.主要技术组织措施 (14) 7.1保证工程质量措施 (14) 7.2安全施工措施 (15) 7.3降低成本措施 (15) 7.4现场文明施工措施 (15) 四、小结 (15) 参考资料 (16) 网页制作课程设计报告 学院： 专业班级： 姓名： 学号： 成绩： 阅卷教师： 目录 1.设计目的 (1) 2.设计思想 (1) 2.1网站整体结构规划思想 (1) 2.2 主页设计思想 (1) 2.3子页的设计思想 (1) 3网页详细设计分析 (1) 4结论 (2) 1.设计目的 阐述该个人网站的设计意图和创意，简单介绍自己的个人网站。 2.设计思想 阐述网站的整体设计思想，包括： 2.1网站整体结构规划思想 要求阐述网站整体结构的选择、设计的思想，绘制网站结构草图。 2.2 主页设计思想 要求对主页的布局思路进行阐述和分析。 2.3子页的设计思想 要求对子页的设计以及网页对象的选取思路进行阐述和分析。 3网页详细设计分析 要求选取一张网页，对网页的设计实现过程进行阐述和分析，详细说明制作该网页的步骤，所使用的网页对象以及该网页对象的操作方法。 4结论 对整个设计报告做归纳性总结，并分析设计过程中的困难及如何解决的，最后提出展望。 一、设计目的 本课程的设计目的是通过实践使同学们经历Dreamweaver cs3开发的全过程和受到一次综合训练，以便能较全面地理解、掌握和综合运用所学的知识。结合具体的开发案例，理解并初步掌握运用Dreamweaver cs3可视化开发工具进行网页开发的方法；了解网页设计制作过程。通过设计达到掌握网页设计、制作的技巧。了解和熟悉网页设计的基础知识和实现技巧。根据题目的要求，给出网页设计方案，可以按要求，利用合适图文素材设计制作符合要求的网页设计作品。熟练掌握Photoshop cs3、Dreamweaver cs3等软件的的操作和应用。增强动手实践能力，进一步加强自身综合素 算法设计与分析实验报告 贪心算法 班级：2013156 学号：201315614 姓名：张春阳哈夫曼编码 代码 #include printf("\n"); for(i=0;i 土木工程施工课程设计 一、工程简介 1、工程概况 某厂金工车间，柱网尺寸为6米，建筑总厂108m，宽42m，设有一道伸缩缝，采用装配式钢筋混凝凝土排架结构，共两跨。低跨柱顶标高8.40m，跨度为18m，配有5T桁车，轻轨标高6m，高跨柱顶标高为11.10m，跨宽为24m，配有10T桁车，轻轨标高8.4m，高跨柱设有天窗架。 1)建筑平面图及剖面见任务书图1。 2)柱子采用预制混凝土工字型断面柱，混凝土为C30，见任务书图2。 3)采用T型断面钢筋混凝土吊车梁及预应力大型屋面板。 4)屋架采用预应力混凝土梯形屋架，混凝土为C40，见任务书图2。 5)采用普通钢筋混凝土地基梁和连续梁。 2、施工条件 1)施工现场已经“三通一平”，基础工程已完；施工现场土质为粘土，其 地基承载力为200kPa。 2)施工单位有两台起重设备使用，一台为W1-100。另一台为W2-200，其 起重性能见任务书附录1。 3)结构构件的制作：要求柱、屋架在现场预制，其余构件如吊车梁、连系 梁、大型屋面板及地基梁等可在距离现场5公里的构件厂制作，采用汽 车运至现场进行安装。 4)施工现场所需人力、材料及设备均可按设计需要给予满足。 5)工期：主体结构安装，其施工日期定为年，月至月，共个 月。施工期间最热月平均气温29.3℃，极端最高温度40℃。 6)结构安装定额见任务书附录2。 7)混凝土强度资料见附录3. 二、施工方案的选择以及施工顺序的设计 1、施工部署 本工程基础和预置工程计划采用分段流水施工。首先施工基础，基坑挖土选择一台0.25m3反铲挖土机挖土，基础，预置工程划分施工段（应自己划分）厂房结构安装选择一台w1-200型履带式起重机作为吊装机具。 根据本工程特点，施工划分为如下几个阶段： 【1】施工准备阶段 （1）技术准备 工程开工前，由技术负责人组织施工技术人员认真熟悉施工图纸，领会设计意图，对施工图进行图纸自审。在图纸自审的基础上，会同，监理进行专业图纸会审。编制各分部分项工程施工作业方案和关键过程作业技术。进行技术交底，制定本工程项目质量计划。配备本工程所需规，标准和资料表格。做好现场交接工作，包括测量控制点，施工用水，电解驳点。专业安装配合土建埋设铁件，埋管，接 Web应用开发技术 实验报告 专业：计算机科学与技术 班级： 学号： 姓名： 一、设计题目 个人网站 二、目的 １、本次设计是学生在学完ASP动态网站开发课程后的一次实践性很强的课程设计，是对ASP进行动态网站开发所学知识的综合运用。 2、掌握使用ASP技术进行网站开发设计。 3、通过本次实习，使学生加深所学知识内容的理解，并能积极地调动学生的学习兴趣，结合实际应用操作环境，真正做到理论与实际相结合。 三、功能需求描述 此网站可以对主人留言，来发表自己的心情，也可以把自己的联系方式写入其中，达到和睦相处、心灵的驿站的目的等。 四、总体设计 五、详细设计 （一）、我的主页 此页面为网站的主页，通过发布新心情，点击通讯录可以查看通讯录好友信息，点击留言板可以查看好友留言。 主要代码： 土木工程施工课程设计完整版
网页制作课程设计报告
算法设计与分析实验报告贪心算法
土木工程课程设计38281
WEB个人主页课程设计