算法实验报告01背包问题.doc
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=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+)迁(j<wij)Vij=Vi-lj;elseif (Vi-1 j>Vi-l j-wi+vi)Vi j=Vi-l j;elseVi j=Vi-l j-wi+vi;/以上构造动态规划表j 二C；for(i=n;i>0;i)if(Vi j>Vi-l j)xi二 1;j=j-wi；elsexi二0;printf (/z动态规划表如下:n"); for(i=0;i<6;i 卄)for(j=0;j<7;j+)printf ("%8d", Vi j);printf("n");printfC装入背包物品：n"); for(i=0;i<6;i卄)printf(”4d",xi);printf ("n背包取得最大值：n");printf ("9Hdn", Vn C);三、实验结果:q| 回力态规划表如下00000直入背包物5b0 0 00continue65算法实埶Debug'动态规那去exe“0n055 51 105020202025353S25352404560四.实验分析:这次实验用到的是动态规划法，0/1背包问题用动态规划法首先要构造动态规划 表，用三个for语句实现；根据动态规划表每行的最大值变化确定每个元素的装 入与否，逐步确定出装入背包的物品，背包容量的最大值也就是动态规划表最右 下角。在本次实验中遇到了动态规划表构造紊乱的状况，经核查是因数组的初始 位置0混淆成1造成的。”01”背包问题的贪心算法一、实验目的与要求：熟悉C/C+语言的集成开发环境：通过本实验加深对贪心算法、动态规划和回溯算法的理解。二、实验容：掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握”0-1”背包问题的 三种算法，并分析其优缺点。三、实验程序：#include"stdio. h"void 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 m, i, j, p, vx, wx, k, ii;int V二0;/总价值初始化/计算单位价值printf (”单位价值为：n");for (m=0;m<5;m+)qm二m;xm=vm /wm;printf ( zx%d=%dt*, m, xm);冒泡排序for(i=0;i<4;i +)for(j=0;j<4-i;j+)if(xj<xj+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单位价值降序为:n"); for(i=0;i<5;i+)printf("x%d=%dt", i, xi); 装入背包for (i=0; i<n&&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:邕法宝執令心Ir'DEbugVa心lre“-更位价直为：x0=8xl=10 X2=15 x3=10 x4J=10鱼位价值降序为：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. 保证物品按单位价值排列后依然能知道他的原始顺序位置，经过几番思考，决定设置一个数组来保存该物品的 原始位置，在冒泡算法交换时同时交换物品编号；2. 装入背包过程如何保证装入不完整物品，即背包剩余容量不能满足完全放入下一个物品。通过本次试验又熟悉了冒泡算法的应用，以及多重foi循环的 应用。”oL背包问题的回溯算法一、实验目的与要求：熟悉C/C+语言的集成开发环境；通过本实验加深对贪心算法、动态规划和回溯算法的理解"二、实验容：掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握”0-1”背包问题的 三种算法，并分析其优缺点。三、实验程序：include <iostream h>/圧义min、max函数int min(int a,int b)if(a>=b) return b;else return a;int max(int a,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;j<jmax;j+)mn j二0;for (int p=wEn:p<=c;p+)mnp=vn;for(int i=n-l;i>l;i)jmax=min(wLi.-l, c);for(int j=0;j<=jmax;j+)mi j=mi+l j;for(int t=wil;t<=c;t+)mit=max(mi+ljt, mFi+lt-wi+vi);ml c二m2 c;if (c>=wl)ml c=max(ml c,m2 c-wl+vl);void Traceback(int m.66, int w6, int c,int n, int x6) for (int i=l;i<n;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;/cin»cl;cout«0-l 背包如下:z/«endl;cout«，?物品的重量分别为:/z«endl;for (int p=l;p<6;p+)cout«wlEp« ”；cout«endl;cout<<"物品的价值分别为："<<endl;for (int q=l;q<6;q+)cout«vlq«/z “；cout«endl;cout«"背包的容量为："«cl«endl;cout<<"要选择的物品是<«endl;Knapsack (vl, wl, cl, nl, t);/for (int i=l; i<=nl; i+) cout«vl i «endl;Traceback (t, wl, cl, nl, xl);for(i=l;i<=nl;i+) if(xli=l) m+=vlLil；cout«* 第"<<i<<"件物品"<endl; cout«，?最大总价值为：/«m«endl; 五.实验分析:本次实验用回溯法解决0/1背包问题，回溯法首先要建立0/1背包的解空间树，然后再回溯得出搜素空间，即解的围，然后求出最佳答案。实验中先构造两个函数,Knapsack列出所有背包的解空间，Traceback对解空间进行搜索，得出答案。
