算法设计-0-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+ai.weight = limitW)copi=1;if(in-1)find(i+1,tw+ai.weight,tv);elsefor(k=0;kmaxv)if(in-1)find(i+1,tw,tv-ai.value);elsefor(k=0;kn;+k)optionk=copk;maxv=tv-ai.value;2.2.2 非递归实现（动态规划法）int knapsack(int &n,int &C,int sM,int pM,int VMM) int i,j; for (i=0;i=n;i+) for(j=0;jj) Vij=Vi-1j; else if(si=j) Vij=max(Vi-1j,Vi-1j-si+pi); return VnC; void traceback(int n,int C,int sM,int xM,int VMM) for(int i=1;i=n;i+) if(ViC=Vi-1C) xi=0; else xi=1; C=C-si; 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) 递归实现：#include #define N 100 /最大物品总种数int n;/物品总种数float limitW;/限制的总重量float totV;/全部物品的总价值float maxv;/解的总价值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);elsefor(k=0;kmaxv)if(in-1)find(i+1,tw,tv-ai.value);elsefor(k=0;kn;+k)optionk=copk;maxv=tv-ai.value;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(选择的物品:);for(k=0;kn;+k)printf(%d,optionk);printf(n总价值为: %f,maxv);getchar(); getchar() ; return 0; (2)非递归实现：#includeusing namespace std;#define max(a,b) ab?a:b#define M 100void display(int &n,int &C,int sM,int pM) int i; coutn; coutendl; coutC; coutendl; coutplease input w:endl; s0=0; for(i=1;isi; coutplease input vendl; p0=0; for(i=1;ipi;int knapsack(int &n,int &C,int sM,int pM,int VMM) int i,j; for (i=0;i=n;i+) for(j=0;jj) Vij=Vi-1j; else if(si=j) Vij=max(Vi-1j,Vi-1j-si+pi); return VnC; void traceback(int n,int C,int sM,int xM,int VMM) for(int i=1;i=n;i+) if(ViC=Vi-1C) xi=0; else xi=1; C=C-si; ;void main() int i,j,n,C; char ch; int sM,pM,xM; int VMM; while(1) display(n,C,s,p); cout运算结果如下：endl; for(i=1;i=n;i+) xi=0; knapsack(n,C,s,p,V); cout ; for(j=0;j=C;j+) coutj ; coutendl; for(i=0;i=n;i+) couti ; for(j=0;j=C;j+) coutVij ; coutendl; cout