《计算机算法基础陶杰》由会员分享，可在线阅读，更多相关《计算机算法基础陶杰（14页珍藏版）》请在金锄头文库上搜索。
1、最大字段和1.实验目的和要求（1）深刻掌握动态规划法的设计思想并能熟练运用；（2）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。 （3）分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法；（4）比较不同算法的时间性能；（5）给出测试数据，写出程序文档2.实验内容给定由 n 个整数组成的序列(a1, a2, , an)，求该序列形如 的子段和的最大 值，当所有整数均为负整数时，其最大子段和为 0。3.实验环境Turbo C 或 VC+4.实验学时2 学时，必做实验5.数据结构与算法数据结构: 程序中所用的数据都是储存在数组当中算法: 蛮力法函数
2、MaxSum(int a,int n,int int i,j,k;for(i=1;isum)sum=asum;besti=i;bestj=j; return sum; void main() int n,a100,m,i,j,maxsum;coutn;coutam;maxsum=MaxSum(a,n,i,j);cout int MaxSum(int a,int left,int right) int sum=0;if (left=right) if (aleft0) sum=aleft;else sum=0;else int center=(left+right)/2;int leftsum=
3、MaxSum(a,left,center);int rightsum=MaxSum(a,center+1,right);int s1=0;int lefts=0;for(int i=center;i=left;i-)lefts+=ai;if(leftss1)s1=lefts;int s2=0;int rights=0;for(int j=center+1;js2)s2=rights;sum=s1+s2;if(sumn;coutam;maxsum=MaxSum(a,1,n);cout void MaxSum(int n,int a) int sum=0;int b=0;for(int i=1;i
4、0) b+=ai;else b=ai;if(bsum) sum=b;coutn;coutam; MaxSum(n,a); 时间性能：T(n)=O(n)背包问题1.实验题目：分别用贪心法法和分支限界法求解背包问题2. 实验内容：0-1 背包问题：给定 n 种物品和一个背包。物品 i 的重量是 Wi，其价值为 Vi，背包的容量为 C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品 i 只有 2 种选择，即装入背包或不装入背包。不能将物品 i 装入背包多次，也不能只装入部分的物品 i。3.实验源程序：（1）贪心法：#include struct good
5、info float p; /物品效益float w; /物品重量float X; /物品该放的数量int flag; /物品编号 ;/物品信息结构体void Insertionsort(goodinfo goods,int n) int j,i;for(j=2;jgoodsi.p)goodsi+1=goodsi;i-;goodsi+1=goods0; /按物品效益，重量比值做升序排列void bag(goodinfo goods,float M,int n) float cu;int i,j;for(i=1;icu)/当该物品重量大与剩余容量跳出break;goodsi.X=1;cu=cu-
6、goodsi.w;/确定背包新的剩余容量if(in;goods=new struct goodinfo n+1;/coutM;coutgoodsi.w;coutgoodsi.p;goodsi.p=goodsi.p/goodsi.w;/得出物品的效益，重量比cout to run agian“ to exit“j; （2）分支限界法：#include #include#define MaxSize 100 /最多结点数typedef struct QNode float weight;float value;int ceng;struct QNode *parent;bool leftChild
7、;QNode,*qnode; /存放每个结点typedef struct qnode QMaxSize; int front,rear;SqQueue; /存放结点的队列SqQueue sq;float bestv=0; /最优解int n=0; /实际物品数float wMaxSize; /物品的重量float vMaxSize;/物品的价值int bestxMaxSize; / 存放最优解qnode bestE;void InitQueue(SqQueue sq.rear=1;bool QueueEmpty(SqQueue sq) /队列是否为空if(sq.front=sq.rear)re
8、turn true;else return false;void EnQueue(SqQueue return ;sq.Qsq.rear=b;sq.rear=(sq.rear+1)%MaxSize;qnode DeQueue(SqQueue if(sq.front=sq.rear)printf(“队列已空!“);return 0;e=sq.Qsq.front;sq.front=(sq.front+1)%MaxSize;return e;void EnQueue1(float wt,float vt, int i ,QNode *parent, bool leftchild)qnode b;if
9、 (i=n) /可行叶子结点if (vt=bestv)bestE=parent;bestxn=(leftchild)?1:0;return;b=(qnode)malloc(sizeof(QNode); /非叶子结点b-weight=wt;b-value=vt;b-ceng=i;b-parent=parent; b-leftChild=leftchild; EnQueue(sq,b); void maxLoading(float w,float v,int c) float wt=0;float vt=0;int i=1; /当前的扩展结点所在的层float ew=0; /扩展节点所相应的当前载
10、重量float ev=0; /扩展结点所相应的价值qnode e=NULL;qnode t=NULL;InitQueue(sq);EnQueue(sq,t); /空标志进队列while (!QueueEmpty(sq) wt=ew+wi; vt=ev+vi;if (wt bestv) bestv=vt;EnQueue1(wt,vt,i,e,true); / 左儿子结点进队列 EnQueue1(ew,ev,i,e,false); /右儿子总是可行；e=DeQueue(sq); / 取下一扩展结点if (e = NULL)if (QueueEmpty(sq) break;EnQueue(sq,NU
11、LL); / 同层结点尾部标志e=DeQueue(sq); / 取下一扩展结点i+;ew=e-weight; /更新当前扩展结点的值ev=e-value;printf(“最优取法为：n“);for( int j=n-1;j0;j-) /构造最优解bestxj=(bestE-leftChild?1:0);bestE=bestE-parent;for(int k=1;k=n;k+)if(bestxk=1)printf(“n 物品%d:重量：%.1f，价值：%.1fn“,k,wk,vk);printf(“n“);printf(“最优价值为：%.1fnn“,bestv);void main()int c;float ewvMaxSize;printf(“ / 0-1 背包问题分枝限界法 /nn“);printf(“请输入物品的数量：n“);scanf(“%d“,printf(“请输入背包的最大承重量：n“);scanf(“%d“,printf(“n 请输入物品的重量和单位重量价值:nn“);for(int i=1;i=n;i+)printf(“物品%d:“,i);scanf(“%f%f“,vi=wi*ewvi;printf(“n“);maxLoading(w, v, c);
