算法设计与分析课程论文

式表明:如果第i个物品的重量小于背包的容量,则会宥一下两种情况:(a)如果把第i个物品装入背包,则背包物品的价值等于第i-1个物品装入容量位j-wi的背包中的价值加上第i个物品的价值vi;(b)如果第i个物品没有装入背包,则背包屮物品价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然,取二荞屮价值最大的作为把前i个物品装入容量为j的背包屮的最优解O3.5.3程序设计C语言实现的主要代码如下:intKnapSackfintn'intw[],intv[],intx[]JntC){inti,j;for(i=0;i<=n;i++)V[i][0)=0;for(j=0;j<=C;j++)V[O][j]=O;for(i=0;i<=n-l;i++)for(j=0;j<=C;j++)if(j<w[i])V[i][j]=V[i-l][j];elseV[i][j]=max(V[i-l][j],V[i-l][j-w[i]]+v[i]);j=C;for(i=n-l;i>=0;i-){if(V[i][j]>V[i-l][j]){x[i]=1;j=j-w[i];}elsex[i]=0;}printf("选中的物品是for(i=0;i<n;i++)printf("%d",x[i]);printf("\n");4.总结递归和动态规划是算法设计屮的重耍方法,它们涉及而很广泛,本文只是对K•进行了初步探讨,还有很多更加深入的东西等着大家去深入研究。作为算法设计的经典方法,它们并不会随着时间的流逝Kij丧失意义,相反,它对我们的算法设计研究提供了重要的思路以及指导。参考文献[1]余祥宣,崔国华,邹海明.计算机算法基础[M].武汉:华中科技大学出版社,2003.[2]BW英,任瑞征,钱宇华.算法设计与分析:淸华大学出版社.[3]应莉0-1竹包问题及其算法计算机勾现代化(2009)06-0024-03.