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

计算机学院高级语言程序设计课程设计报告学号2016-2017学年 第二学期1608220203高级语言程序设计课程设计报告题目：背包问题专业：网络工程（对口）班级：16（3）班姓名：代应豪指导教师：程庆成绩：计算机学院2017 年 4月 25 日一 需求分析背包问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？ 即：假设有一个能装入总体积为T的背包和n件体积分别为w1 , w2 , , wn 的物品能否从n件物品中挑选若干件恰好装满背包即使w1 +w2 + + wn=T要求找出所有满足上述条件的解。例如当T=10各件物品的体积184352时可找到下列4组解 1432 145 82 352。 二 总体设计1.首先声明头文件和常量2.写一个函数，用来得到多个最优解3.使用非递归的算法来求解mij 4再编写一个函数，用来寻找最优解5写个函数，用来输出最优解三 详细设计四 测试五 设计总结问题一:无法读取文txt文件。困难就是txt无法读取，输入路径后没有文件显示。解决办法是，向老师求助。最后，在老师细心的指导下，才知道是自己的计算机操作水平缘故，没有很好的了解计算机路径结构，最后做出了一定的修改，才得以实现。问题二：程序错误。这是一个比较典型的错误，通过查阅书本相关资料。才发觉是函数相关问题，没有能够很好的理解函数思想，导致程序运行错误。六 参考文献1.C语言程序设计（第四版）谭浩强 著2.C语言函数手册，机械工业出版社，1999七 源程序#include#define NUM 10/* 定义物品总数*/#define CONTENT 10 /*定义包的容量*/void knapsack(int vNUM,int wNUM,int c,int mNUM CONTENT) int n=NUM-1; int i,j; int jMax; if(wn-1) c)jMax = wn-1; elsejMax = c; /* 初始化mnj */ for(j = 0; j = jMax; j+)mnj = 0; for(j = jMax +1; j 0; i-) if(wi-1) c) jMax = wi-1; else jMax = c; for(j = 0; j = jMax; j+) mij = mi+1j ; for(j = jMax +1; j = (mi+1j-wi+vi) mij = mi+1j ; elsemij = mi+1j-wi+vi; if(cw0) if(m1c = (m1c-w0+v0) m0c= m1c; elsem0c= m1c-w0+v0; else m0c= m1c;void traceback(int flagNUM,int wNUM,int mNUMCONTENT)int n = NUM -1;int i;int c = CONTENT;for(i = 0; i 0) flagn = 1;else flagn = 0;void printResult(int flagNUM,int wNUM,int vNUM,int mNUMCONTENT)int i;printf(the knapsack should contain:n);printf( num weight value n);for(i = 0;i NUM; i+)if(flagi = 1) printf( %d %d %dn,i,wi,vi);printf(the max value in the knapsack is: %dn,m0CONTENT);int main()int valueNUM=5,2,3,4,3,6,5,7,8,2;int weightNUM=2,1,3,2,4,3,5,6,2,2;int c = CONTENT;int maxvalueNUMCONTENT;int flagNUM=0,0,0,0,0,0,0,0,0,0;printf(*n); printf(* this program will solve *n); printf(* the problem of 0-1knapsack *n); printf(*n);/*计算最优值*/knapsack(value,weight,c,maxvalue);/*构造最优解*/t