数据结构与算法分析专题实验.doc

《数据结构与算法分析专题实验.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.交通大学数据结构与算法课程实验实验名称：数据结构与算法课程专题实验所属学院：电信学院专业班级：计算机32班小组成员：指导老师：仲孟教授实验一背包问题的求解1.问题描述假设有一个能装入总体积为T的背包和n件体积分别为w1,w2,…wn的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1+w2+…+wm=T，要求找出所有满足上述条件的解。例如：当T=10，各件物品的体积{1,8,4,3,5,2}时，可找到下列4组解：(1,4,3,2)word范文.(1,4,5)(8,2)(3,5,2)。2.实现提示可利用回溯法的设计思想来解决背包问题。首先，将物品排成

2、一列，然后，顺序选取物品装入背包，若已选取第i件物品后未满，则继续选取第i+1件，若该件物品“太大”不能装入，则弃之，继续选取下一件，直至背包装满为止。如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入的物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直到求得满足条件的解，或者无解。由于回溯求解的规则是“后进先出”，自然要用到“栈”。3.问题分析1、设计基础            后进先出，用到栈结构。 2、分析设计课题的要求，要求编程实现以下功能：        a．从n件物品中挑选若干件恰好装满背包 b

3、.要求找出所有满足上述条件的解，例如：当T=10，各件物品的体积{1，8，4，3，5，2}时，可找到下列4组解：（1，4，3，2）、（1，4，5）、（8，2）、（3，5，2）3，要使物品价值最高，即p1*x1+p2*x1+...+pi*xi(其1<=i<=n，x取0或1，取1表示选取物品i) 取得最大值。 在该问题中需要决定x1 .. xn的值。假设按i = 1，2，...，n 的次序来确定xi 的值。如果置x1 = 0，则问题转变为相对于其余物品(即物品2，3，.，n)，背包容量仍为c 的背包问题。若置x1 = 1，问题就变为关于最大背包容量为c-w1

4、 的问题。现设r={c，c-w1} 为剩余的背包容量。在第一次决策之后，剩下的问题便是考虑背包容量为r 时的决策。不管x1 是0或是1，[x2 ，.，xn ] 必须是第一次决策之后的一个最优方案。也就是说在此问题中，最优决策序列由最优决策子序列组成。这样就满足了动态规划的程序设计条件。4.问题实现代码1：#include"iostream"usingnamespacestd;classLink{public:intm;Link*next;Link(inta=0,Link*b=NULL){m=a;next=b;}};classLStack{private:

5、Link*top;word范文.intsize;inta[100];public:LStack(intsz=0){top=NULL;size=0;a[0]=0;}~LStack(){clear();}voidclear(){while(top!=NULL){Link*temp=top;top=top->next;deletetemp;}size=0;}voidpush(intit,intb){top=newLink(it,top);a[size]=b;size++;}intpop(){intit=top->m;Link*ltemp=top->next;d

6、eletetop;top=ltemp;size--;returnit;}inttopValue(){returntop->m;}intlength(){returnsize;}intsum(){ints=0;for(inti=0;ipop(

7、)+1;isum()+x2[i]<=x1){x4->push(i,x2[i]);}if(x4->sum()==x1){x4->print();break;}}if(x4->length()==1&&x4->topValue()==n-1)return;elsepanduan(x1,n,x2,x4);}intmain(){LStack*ll=newLStack(0);intm[100];intn,z;cout<<"输入物品个数"<>n;cout<<"输入物品大小"<

8、i++)cin>>m[i];cout<<"输入背包大小"<>