c背包问题-课程设计报告

计算机学院《高级语言程序设计》课程设计报告1学号1608220203《高级语言程序设计》课程设计报告题目：背包问题专业：网络工程（对口）班级：16（3）班姓名：代应豪指导教师：程庆成绩：计算机学院2017年4月25日2016-2017学年第二学期计算机学院《高级语言程序设计》课程设计报告2一需求分析背包问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？即：假设有一个能装入总体积为T的背包和n件体积分别为w1,w2,…,wn能否从nw1+w2+…+wn=TT=10{184352}4143214582352计算机学院《高级语言程序设计》课程设计报告3二总体设计1.首先声明头文件和常量2.写一个函数，用来得到多个最优解3.使用非递归的算法来求解m[i][j]4再编写一个函数，用来寻找最优解5写个函数，用来输出最优解计算机学院《高级语言程序设计》课程设计报告4三详细设计四测试计算机学院《高级语言程序设计》课程设计报告5五设计总结问题一:无法读取文txt文件。困难就是txt无法读取，输入路径后没有文件显示。解决办法是，向老师求助。计算机学院《高级语言程序设计》课程设计报告6最后，在老师细心的指导下，才知道是自己的计算机操作水平缘故，没有很好的了解计算机路径结构，最后做出了一定的修改，才得以实现。问题二：程序错误。这是一个比较典型的错误，通过查阅书本相关资料。才发觉是函数相关问题，没有能够很好的理解函数思想，导致程序运行错误。六参考文献1.C语言程序设计（第四版）谭浩强著2.C语言函数手册，机械工业出版社，1999七源程序#includestdio.h#defineNUM10/*定义物品总数*/#defineCONTENT10/*定义包的容量*/voidknapsack(intv[NUM],intw[NUM],intc,intm[NUM][CONTENT]){intn=NUM-1;inti,j;intjMax;if((w[n]-1)c)计算机学院《高级语言程序设计》课程设计报告7jMax=w[n]-1;elsejMax=c;/*初始化m[n][j]*/for(j=0;j=jMax;j++)m[n][j]=0;for(j=jMax+1;j=c;j++)m[n][j]=v[n];/*使用非递归的算法来求解m[i][j]*/for(i=n-1;i0;i--){if((w[i]-1)c)jMax=w[i]-1;elsejMax=c;for(j=0;j=jMax;j++)m[i][j]=m[i+1][j];for(j=jMax+1;j=c;j++){if(m[i+1][j]=(m[i+1][j-w[i]]+v[i]))m[i][j]=m[i+1][j];else计算机学院《高级语言程序设计》课程设计报告8m[i][j]=m[i+1][j-w[i]]+v[i];}}if(cw[0]){if(m[1][c]=(m[1][c-w[0]]+v[0]))m[0][c]=m[1][c];elsem[0][c]=m[1][c-w[0]]+v[0];}elsem[0][c]=m[1][c];}voidtraceback(intflag[NUM],intw[NUM],intm[NUM][CONTENT]){intn=NUM-1;inti;intc=CONTENT;for(i=0;in;i++){if(m[i][c]==m[i+1][c])计算机学院《高级语言程序设计》课程设计报告9flag[i]=0;else{flag[i]=1;c-=w[i];}}if(m[n][c]0)flag[n]=1;elseflag[n]=0;}voidprintResult(intflag[NUM],intw[NUM],intv[NUM],intm[NUM][CONTENT]){inti;printf(theknapsackshouldcontain:\n);printf(numweightvalue\n);for(i=0;iNUM;i++){if(flag[i]==1)printf(%d%d%d\n,i,w[i],v[i]);}计算机学院《高级语言程序设计》课程设计报告10printf(themaxvalueintheknapsackis:%d\n,m[0][CONTENT]);}intmain(){intvalue[NUM]={5,2,3,4,3,6,5,7,8,2};intweight[NUM]={2,1,3,2,4,3,5,6,2,2};intc=CONTENT;intmaxvalue[NUM][CONTENT];intflag[NUM]={0,0,0,0,0,0,0,0,0,0};printf(****************************************\n);printf(*thisprogramwillsolve*\n);printf(*theproblemof0-1knapsack*\n);printf(****************************************\n);/*计算最优值*/knapsack(value,weight,c,maxvalue);/*构造最优解*/traceback(flag,weight,maxvalue);/*打印程序的结果*/printResult(flag,weight,value,maxvalue);getch();return0;计算机学院《高级语言程序设计》课程设计报告11}