数据结构专题实验.docx

蚂实验目的薇通过实验更好的理解、应用本学期数据结构所学知识,例如线性表、树、图、排序、查找、索引。将三大结构和两个应用融会贯通,理论运用于实践。薆在实验中提高自身的编程能力,同时学会比较不同程序的时间空间成本,力求写出更加优质的程序。螃养成用所学知识解决实际问题的习惯,学以致用而不是死学知识。螀实验内容羆背包问题的求解【栈(线性表)】芆问题描述螄假设有一个能装入总体积为T的背包和n件体积分别为w1,w2,…wn的物品,能否从n件物品中挑选若干件恰好装满背包,即使w1+w2+…+wm=T,要求找出所有满足上述条件的解。衿例如:当T=10,各件物品的体积{1,8,4,3,5,2}时,可找到下列4组解:虿 (1,4,3,2)肆 (1,4,5)薂 (8,2)芁 (3,5,2)。聿基本要求螇设计基础:堆栈蚃分析设计课题的要求,要求编程实现以下功能:荿<1>从n件物品中挑选若干件恰好装满背包薈<2>要求找出所有满足上述条件的解,例如:当T=10,各件物品的体积{1,8,4,3,5,2}时,可找到下列4组解:(1,4,3,2)、(1,4,5)、(8,2)、(3,5,2)。芃算法分析螄首先将n件物品排成一列,依次选取;若装入某件物品后,背包内物品的总质量不超过背包最大装载质量时,则装入(进栈);否则放弃这件物品的选择,选择下一件物品试探,直至装入的物品总和正好是背包的最大转载质量为止。这时我们称背包装满。螂若装入若干物品的背包没有满,而且又无其他物品可以选入背包,说明已装入背包的物品中有不合格者,需从背包中取出最后装入的物品(退栈),然后在未装入的物品中挑选,重复此过程,直至装满背包(有解),或无物品可选(无解)为止。羈实验代码羄#include"iostream"薂usingnamespacestd;袀template<classElem>classStack莇{螄 private:薃 intsize;罿 inttop;袆 public:蒄 Elem*listArray;蚅 Stack(intsz=DefaultListSize)莁{芆 size=sz;芅 top=0;蒂 listArray=newElem[sz];葿}罿~Stack()羅{蒃 delete[]listArray;袂}莈 voidclear()螅{top=0;}芁 boolpush(constElem&item)羀{螈 if(top==size)蒆 returnfalse;莂 else肈{芇 listArray[top++]=item;膆 returntrue;莃}蒁}蚇 intpop(Elem&it)羇{膁 if(top==0)return-1;蕿 else肆{蚇 it=listArray[--top];节 returnit;袂}蝿}膃 inttopvalue(Elem&it)const莄{肀 if(top==0)腿 return-1;羄 else膁{膈 it=listArray[top-1];蚈 returnit;蚄}膂}蒁 intlength()const肇{returntop;}莄};芄intmain()虿{蒇 Stack<int>beibao(100);膅 intweight[100],n,T;肁 inti=0,k=0,a[100];羂 cout<<"请输入背包总体积T:";袆 cin>>T;袅 cout<<"请输入物品件数n:";芀 cin>>n;芈 cout<<"请输入物品质量weight:";螇 for(i=0;i<n;i++)袃 cin>>weight[i];莂 do{蒆while(T>0&&k<n){芇if(T>=weight[k]){//(weight[k]);腿T-=weight[k];螈}蚆k++;//不符合则考察下一个背包莄}膀if(T==0){//找到一种方法,输出袇cout<<"找到方法:";肆for(i=0;i<();i++)肅{节cout<<[i]<<"";艿}