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

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

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

2、1)find(i+1,tw+a[i].weight,tv);else{for(k=0;kmaxv){if(i

3、i,j;for(i=0;i<=n;i++)for(j=0;j<=C;j++){if(i==0

4、

5、j==0)V[i][j]=0;elseif(s[i]>j)V[i][j]=V[i-1][j];elseif(s[i]<=j)V[i][j]=max(V[i-1][j],V[i-1][j-s[i]]+p[i]);}returnV[n][C];};voidtraceback(intn,intC,ints[M],intx[M],intV[M][M]){for(inti=1;i<=n;i++){if(V[i][C]==V[i-1][C])x[i]=0;else{x[i]=1;C=C-s[i];}}

6、}2.3、编程实现题目要求；2.4、调试程序；2.5、实验数据及实验结果；2.5.1递归方法：输入数据：背包容量为50公斤。物品1重10公斤，价值60元；物品2重20公斤，价值100元；物品3重30公斤，价值120元。输出结果：2.5.2非递归方法：输入数据：背包容量为50公斤。物品1重10公斤，价值60元；物品2重20公斤，价值100元；物品3重30公斤，价值120元。输出结果：2.6、算法时间复杂度2.6.1递归方法：O(n3)2.6.2非递归方法：O(n3)三、总结通过本次实验，让我意识到我对编程的不足,但也了解到自己的成长空间还很大。附录：源代码(1)递归实现：#includ

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

8、ght,tv);else{for(k=0;kmaxv){if(i

9、scanf("%f",&w);a[k].weight=w;}printf("输入各物品的价值:");for(totV=0.0,k=0;k