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

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

2、1)find( i +1, tw+a i .weight, tv);elsefor (k=0;kmaxv)if (i n-1)find( i +1, tw, tv -a i .value);else for (k=0;kn;+k)opti on k=copk;maxv=v -a i .value;2.2.2非递归实现(动态规划法)int knapsack( int &n, int &C, int sM, int pM, int V M【M)inti,j;for (i=0;i=n;i+)for (j=0;jj)Vij=Vi-1j；else if (si=j)Vij=maXW-1j,Vi-1j-s

3、i+ pi);return V n q；void traceback( int n, int q int s M, int x M, int VM【M) for (int i=1;i8 100 120输出结果:2.6、算法时间复杂度2.6.1递归方法：0( n3)2.6.2非递归方法：0( n3)三、总结通过本次实验，让我意识到我对编程的不足，但也了解到自己的成长空间还很大。附录：源代码(1)递归实现：#i nclude #defi ne N 100 /最大物品总种数int n;物品总种数float limitW;/限制的总重量float totV;/全部物品的总价值float maxv;/解

4、的总价值int optionN; 解的选择int copN;/当前解的选择struct /物品结构float weight;float value;aN;void find(int i,float tw,float tv)int k;/物品i包含在当前方案的可能性if(tw+ai.weight = limitW)copi=1;if(in-1)find(i+1,tw+ai.weight,tv);else for(k=0;kmaxv)if(in-1) find(i+1,tw,tv-ai.value);elsefor(k=0;kn;+k) optionk=copk; maxv=tv-ai.value

5、;int main()int k;float w,v;printf( 输入物品种数 :); scanf(%d,&n);printf( 输入各物品的重量 :); for(k=0;kn;+k) scanf(%f,&w);ak.weight = w;printf( 输入各物品的价值 :); for(totV=0.0,k=0;kn;+k) scanf(%f,&v);ak.value = v; totV += v;printf( 输入限制重量 :); scanf(%f,&limitW);maxv=0.0; for(k=0;kn;+k)copk=0; find(0,0.0,totV);printf(”选择

6、的物品:”); for(k=0;k n;+k) prin tf(%d,optio nk);printf(n 总价值为：f,maxv); getchar();getchar();return 0;(2)非递归实现：#include using namespacestd;#defi ne maXa,b) ab?a:b#defi ne M100void display( int &n, int &C, int sM, int pM)int i;coutn;coute ndl;cout Ccoute ndl;cout please in put w:e ndl;s0=0;for (i=1;i si;c

7、out please in put ve ndl;p0=0;for (i=1;i pi;int knapsack( int &n, int &C, int sM, int pM, int V M【M) int i,j;for (i=0;i= n;i+)for (j=0;jj)Vij=Vi-1j;else if (si=j)Vij=maXW-1j,Vi-1j-si+pi); returnVn q;void traceback( int n, int C int s M, int x M, int V M M)for (int i=1;i= n;i+)if (Vi q=Vi-1 q)xi=0；C=C si; ；void main()int i,j,n,C;char ch;int s M,P【M,x M；int V M M;while (1)display( n,C,s,p);cout运算结果如下：e ndl;for (i=1;i=n;i+)xi=0;kn apsack (n ,C,s,p,V);cout ;for (j=0;j=C;j+)coutvvjvv ;coute ndl;for (i=0;i=n;i+)coutvvivv ;for (j=0;j=C;j+) coutVijcoute ndl;coute ndl;COUt