算法实验报告01背包问题

1、3业尢学皆算机科学乡荻付学陵算法分析与设计实验报告实验：0/1背包问题学号:班级:”01”背包问题的动态规划算法一、实验目的与要求：熟悉C/C+语言的集成开发环境：通过本实验加深对贪心算法、动态规划和回溯算法的理解。二、实验容：掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握”0-1”背包问题的 三种算法，并分析其优缺点。三、实验程序：#includestdio. hint n=5;int w=0, 3, 2, 1, 4, 5;int v=0, 25,20,15,40, 50;int x5;int V67;int C=6;void main(void)int i, j；for (i

2、=0;i=n;i+)Vi0二 0;for(j二O;j=C;j+)VOj=O;for(i=l;i=n;i+)for(j=l;j=C;j+)迁(jVi-l j-wi+vi)Vi j=Vi-l j;elseVi j=Vi-l j-wi+vi;/以上构造动态规划表j 二C；for(i=n;i0;i)if(Vi jVi-l j)xi二 1;j=j-wi；elsexi二0;printf (/z动态规划表如下:n); for(i=0;i6;i 卄)for(j=0;j7;j+)printf (%8d, Vi j);printf(n);printfC装入背包物品：n); for(i=0;i6;i卄)printf

3、(”4d,xi);printf (n背包取得最大值：n);printf (9Hdn, Vn C);三、实验结果:q| 回力态规划表如下00000直入背包物5b0 0 00continue65算法实埶Debug动态规那去exe“0n055 51 105020202025353S25352404560四.实验分析:这次实验用到的是动态规划法，0/1背包问题用动态规划法首先要构造动态规划 表，用三个for语句实现；根据动态规划表每行的最大值变化确定每个元素的装 入与否，逐步确定出装入背包的物品，背包容量的最大值也就是动态规划表最右 下角。在本次实验中遇到了动态规划表构造紊乱的状况，经核查是因数组的初

4、始 位置0混淆成1造成的。”01”背包问题的贪心算法一、实验目的与要求：熟悉C/C+语言的集成开发环境：通过本实验加深对贪心算法、动态规划和回溯算法的理解。二、实验容：掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握”0-1”背包问题的 三种算法，并分析其优缺点。三、实验程序：#includestdio. hvoid main(void)int C二6;/背包容量6int n=5;/5 个物品int w = 3, 2, 1, 4, 5;物品重量int v = 25, 20,15,40, 50;/物品价值int x = 0, 0, 0, 0, 0;/单位价值初始化int q5;int

5、 m, i, j, p, vx, wx, k, ii;int V二0;/总价值初始化/计算单位价值printf (”单位价值为：n);for (m=0;m5;m+)qm二m;xm=vm /wm;printf ( zx%d=%dt*, m, xm);冒泡排序for(i=0;i4;i +)for(j=0;j4-i;j+)if(xjxj+l)交换单位价值P二xj;xj=xj+l;xj+l=p;/交换价值对应位垃 VX二vj;vj=vj+l; vj+l=vx;交换重量对应位置 WX二wj;wj二wj+l; wLj+l_=wx;交换商品编号 m二qj；qj二qj+l； qj+l二m;printf (n单

6、位价值降序为:n); for(i=0;i5;i+)printf(x%d=%dt, i, xi); 装入背包for (i=0; in&wi C; i+)辻(wi=C)V+=vi;C二C-wi;k=i;辻(C!=0)V+二vi*C/wi;c=0；for(ii=0;ii=k;ii+)printf (n放入第(1个物品：n物品的重量为：%dn物品的价值为：%dn背包 剩余容量为:%dnz，, qii+l, wii, vii, C);printf (”n 总价值为:V);四、实验结果:旨 D:邕法宝執令心IrDEbugVa心lre“-更位价直为：x0=8xl=10 X2=15 x3=10 x4J=10鱼

7、位价值降序为：x0=15 xLl=10 xL2=10 xE3=10 x4J=80 220. 殆为为量 1-4号-容 M重价余 第的的剰n 口%I/ 沂为为量 计量値容 /重价余 第的的剩 入品番04 4!忌仙值为：65 Press any key to continue五、实验分析：本次实验是以贪心算法解决背包问题，贪心算法要求出每个物 品的单位价值，根据单位价值降序排列，再依次装入背包。当 最后一个物品不能完全装入时，装入部分使背包容量为0。在本次实验中，遇到几个难题：1. 保证物品按单位价值排列后依然能知道他的原始顺序位置，经过几番思考，决定设置一个数组来保存该物品的 原始位置，在冒泡算法

8、交换时同时交换物品编号；2. 装入背包过程如何保证装入不完整物品，即背包剩余容量不能满足完全放入下一个物品。通过本次试验又熟悉了冒泡算法的应用，以及多重foi循环的 应用。”oL背包问题的回溯算法一、实验目的与要求：熟悉C/C+语言的集成开发环境；通过本实验加深对贪心算法、动态规划和回溯算法的理解二、实验容：掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握”0-1”背包问题的 三种算法，并分析其优缺点。三、实验程序：include /圧义min、max函数int min(int a,int b)if(a=b) return b;else return a;int max(int a

9、,int b)if(a=b) return a;else return b;void Knapsack(int v6, int w6, int c, int n, int m66)/int jmax=min(wn-l, c);for(int j=0;jjmax;j+)mn j二0;for (int p=wEn:pl;i)jmax=min(wLi.-l, c);for(int j=0;j=jmax;j+)mi j=mi+l j;for(int t=wil;t=wl)ml c=max(ml c,m2 c-wl+vl);void Traceback(int m.66, int w6, int c,i

10、nt n, int x6) for (int i=l;in;i+)if(mic=mi+lc) xi=0;elsexi二1;c-=wLi;xn=(mn c !=0)?l:0;void mainOint nl=5;int cl=6;int wl 6 = 0, 3, 2, 1, 4, 5;int vl6 = 0, 25,20, 15,40,50;int t 6 6;int xl6;int m=0;/cout请输入背包的容量：endl;/cincl;cout0-l 背包如下:z/endl;cout，?物品的重量分别为:/zendl;for (int p=l;p6;p+)coutwlEp ”；coutendl;cout物品的价值分别为：endl;for (int q=l;q6;q+)coutvlq/z “；coutendl;cout背包的容量为：clendl;cout要选择的物品是endl;Knapsack (vl, wl, cl, nl, t);/for (int i=l; i=nl; i+) coutvl i endl;Traceback (t, wl, cl, nl, xl);for(i=l;i=nl;i+) if(xli=l) m