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

1、华南农业大学算法分析与设计课程实验专业年级：10信息与计算科学2班学生学号：22号学生姓名：梁高鼎实验题目：用动态规划法求解0-1背包问题指导老师： 梁 茹 冰实验时间： 012年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=l;if(i<

2、n-l)find(i+1 ,tw+ai .weight,tv);elsefor(k=0;k<n;+k)optionk=copk; maxv=tv;copi=0;物品i不包含在当前方案的可能性 if(tv-ai. value>max v)if(i<n-l)find(i+1 ,tw,tv-ai .value);elsefor(k=0;k<n;+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;f

3、or (i=0;i<=n;i+)for(j=0;j<=c;j+)if(i=o|j=o)vi|j=o;else if(si>j)vij=vi-lj;else if(si<=j)viu=max(vi-lu,vi-lj-si+pi);return vnc;void traceback(int n,int cjnt sm,int xm,int vmm)for(int i=l;i<=n;i+)if(vfic=vi-lc)xi=o；elsexi=l； c=c-si;2.3、编程实现题忖要求；2.4、调试程序；2.5、实验数据及实验结果；2.5.1递归方法：输入数据：背包容量为

4、50公斤。物品1重10公斤，价值60元；物品2重20公斤, 价值100元；物品3重30公斤，价值120元。魏入物晶沖数：3输入各初品的重 = 10 20 30 输入各桝品的价100 120 輪入限罰重量隔输岀结果:2.5.2非递归方法：输入数据：背包容量为50公斤。物品1重10公斤，价值60元；物品2重20公斤, 价值100元；物品3重30公斤，价值120元。pleaseinputn ：3pleaseinputtw：50pleaseinput110 20 30ipleaseinputv60 100120输出结果:2.6、算法时间复杂度2.6.1递归方法：o(n3)2.6.2非递归方法：o(n3

5、)三、总结通过本次实验，让我意识到我对编程的不足，但也了解到自己的成长空间还很大。附录：源代码(1)递归实现：#include <stdio.h>#definen 100 最大物品总种数 intn;/物品总种数float limitw;/限制的总重量float totv;/全部物品的总价值 float maxv;/解的总价值 int optionn;/解的选择 int copn;/当前解的选择 struct /物品结构float weight;float value;anj;void find(int i,float tw,float tv)int k;物品i包含在当前方案的可能性

6、 if(tw+ai.weight <= limitw) copij=l;if(i<n-l)find(i+l,tw+ai weight,tv); elsefor(k=0;k<n;+k)optionk=copk; maxv=tv;copi=0;物品i不包含在当前方案的可能性if(tv-ai. value>max v)if(i<n-l)find(i+1 ,tw,tv-ai .value);elsefor(k=0;k<n;+k) optionk=copk;maxv=tv-ai .value;int main()int k;float w,v;printfc输入物品种

7、数:”)； scanf(”d“,&n);printf(u输入各物品的重量:”);for(k=0;k<n;+k) scanf(m%f&w);ak.weight = w;printf(“输入各物品的价值:”); for(totv=0.0,k=0;k<n;+k) scanf(m%f*,&v);ak.value = v;totv += v;printf(u输入限制重量:”)； scanf(” f,&limitw); maxv=0.0;for(k=0;k<n;+k)copk=0; find(0,0.0,totv);print"选择的物品:”);

8、for(k=0;k<n;+k)printf(n%dm,optionk);printf(un 总价值为:%f*,maxv);getchar();getchar();return 0;(2)非递归实现：# include<iostream>using namespace std;#define max(a,b) a>b?a:b#define m 100void display(int &n,int &c,int sm,int pm)int i;cout«nplease input n:h;cin»n;cout«endl;cout

9、«nplease input tw:n;cin»c;cout«e ndl;cout«nplease input w:n«endl;s0=0;for(i=l;i<=n;i+)cin»si;cout«hplease input vh«endl;p0=0;for(i=l;i<=n;i+)cin»pfi;int knapsack(int &n,int &c,int sm,int pm,int vmmj)int i,j；for (i=0;i<=n;i+)for(j=0;j<=

10、c;j+)if(i=o|j=o)vilj=o；else if(si>j)viuj=vi-lu;else if(si<=j)viu=max(vi-l|j,vi-lu-si+pi);return vnc;；void traceback(int n,int c,int sm,int xm,int vmmj) for(int i=l;i<=n;i+)if(vic=vi-lc)xi=o;elsexi=l；c=c-si;；void main()int i,j,n,c; char ch;int sm,pm,xm;int vmmj;while(l) display(n,c,s,p);cout

11、«h运算结果如下:"«endl; for(i=l;i<i+)xi=0;knapsack(n,c,s,p,v);cout«" ”；fo 珀二 0;jv 二 c;j+)cout«j«h ”； cout«endl;for(i=0;i<=n;i+)cout«i«" ”；for(j=0;j<=c;j+)cout«vij«h ”；cout«endl; cout«endl;cout«h选择的物体向量表示为:"；cout&#