算法设计与分析课程设计报告-背包问题的设计与实现

《算法设计与分析课程设计报告-背包问题的设计与实现》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、湖南理工学院课程论文论文题目0-1背包问题的设计与实现课程名称数据结构与算法设计姓名学号专业班级年级2014级学院计算机学院日期2015年6月25日课程论文评价标准指标评价内容评价等级（分值）得分ABCD选题选题是否新颖；是否有意义；是否与本门课程相关。20-1615-1110-65-0论证思路是否清晰；逻辑是否严密；结构是否严谨；研究方法是否得当；论证是否充分。20-1615-1110-65-0文献文献资料是否翔实；是否具有代表性。20-1615-1110-65-0规范文字表达是否准确、流畅；是否符合学术道德规范。20-1615-1110-65-0能力是否运

2、用了本门课程的有关理论知识；是否体现了科学研究能力。20-1615-1110-65-0评阅教师签名：年月日总分：9目录1.问题描述·······························32.算法设计分析···························33.程序编码与调试分析·····················54.9测试结果·······························71.自学知识·······························72.课程设计心得体会·······················83.参考文献

3、·······························891.问题描述给定n种物品和一个背包，物品i的重量是wi，其价值为vi，背包容量为C。在选择装入背包的物品时，对每种物品i只有两种选择：装入背包或不装入背包，即不能将物品i装入背包多次，也不能只装入物品i的一部分。问：如何选择装入背包的物品，使得装入背包中物品的总价值最大？2.算法设计与分析算法分析在0-1背包问题中，物体被装入一个背包，或者不被装入背包，设xi表示物品i装入背包的情况，则当xi=0时，表示物品i没有被装入背包，xi=1时，表示物品i被装入背包。假设有五个物品，其重量分别是{2，2

4、，6，5，4}，价值分别是{6，3，5，4，6}，背包的容量为10。根据动态规划函数，用一个(n+1)×(C+1)的二维表V，V[i][j]表示把前i个物品装入容量为j的背包中获得的最大价值。按下述方法来划分阶段：第一阶段，只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；第二阶段，只装入前29个物品，确定在各种情况下的背包能够得到的最大价值；依此类推，直到第n个阶段。最后，V(n,C)便是在容量为C的背包中装入n个物品时取得的最大价值。为了确定装入背包的具体物品，从V(n,C)的值向前推，如果V(n,C)>V(n-1,C)，表明第n个物品被装入背包

5、，前n-1个物品被装入容量为C-wn的背包中；否则，第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(intn,intw[],intv[]){for(i=0;i<=n;i++)//初始化第0列V[i][0]=0;

6、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(j0;i--){if(V[i][j]>V[i-1][j]){x[i]=1;j=j-w[i];}elsex[i]=0;}returnV[n][C];//返回背包取得的最大价值}91.程序编码与调试分析程序

7、编码#include#includeintmax(intx,inty){if(x>=y)returnx;elsereturny;}intKnapSack(intn,intC,int*w,int*v,intV[][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

8、[j];elseV[i][j]=max