算法设计背包问题用动态规划的递归实现与非递归实现

《算法设计背包问题用动态规划的递归实现与非递归实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、华南农业大学《算法分析与设计》课程实验专业年级：10信息与计算科学2班学生学号：22号学生姓名：梁高鼎实验题目：用动态规划法求解0-1背包问题指导老师：梁茹冰实验时间：012年11月5日一、实验内容用动态规划法求解0-1背包问题要求：(1)用递归实现(备忘录方法)(2)用非递归实现(动态规划法)二、实验步骤2.1、理解算法思想和问题要求；2.2、写出每个操作的算法2.2.1递归实现(备忘录方法)voidfind(inti,floattw,floattv){intk;〃物品i包含在当前方案的可能性if(tw+a[i].w

2、eight<=limitW){cop[i]=l;if(imaxv){if(i

3、态规划法)intknapsack(int&n,int&C,ints[M],intp[M],intV[M][M]){inti,j;for(i=0;i<=n;i++)for(j=0;j<=C;j++)if(i==O

4、[j==O)V[i]

5、j]=O;elseif(s[i]>j)V[i][j]=V[i-l][j];elseif(s[i]<=j)V[i]U]=max(V[i-l]U],V[i-l][j-s[i]]+p[i]);}returnV[n][C];voidtraceback(intn,intCJnts[M],intx[M

6、],intV[M][M])for(inti=l;i<=n;i++){if(Vfi][C]=V[i-l][C])x[i]=o；elsex[i]=l；C=C-s[i];2.3、编程实现题忖要求；2.4、调试程序；2.5、实验数据及实验结果；2.5.1递归方法：输入数据：背包容量为50公斤。物品1重10公斤，价值60元；物品2重20公斤,价值100元；物品3重30公斤，价值120元。魏入物晶沖数：3输入各初品的重＞=102030输入各桝品的价100120輪入限罰重量隔输岀结果:2.5.2非递归方法：输入数据：背包容量为50公

7、斤。物品1重10公斤，价值60元；物品2重20公斤,价值100元；物品3重30公斤，价值120元。pleaseinputn：3pleaseinputtw：50pleaseinput1102030IpleaseinputV60100120输出结果:2.6、算法时间复杂度2.6.1递归方法：O(n3)2.6.2非递归方法：O(n3)三、总结通过本次实验，让我意识到我对编程的不足，但也了解到自己的成长空间还很大。附录：源代码(1)递归实现：#include#defineN100〃最大物品总种数intn;//

8、物品总种数floatlimitW;//限制的总重量floattotV;//全部物品的总价值floatmaxv;//解的总价值intoption[N];//解的选择intcop[N];//当前解的选择struct{//物品结构floatweight;floatvalue;}a[NJ;voidfind(inti,floattw,floattv){intk;〃物品i包含在当前方案的可能性if(tw+a[i].weight<=limitW)cop[ij=l;if(i

9、);else{for(k=0;kmaxv){if(i

10、量:”);for(k=0;k