算法分析与设计实验报告ex2..doc

实验报告 课程 计算机算法设计与分析 实验名称 最大子段和、0-1背包问题 学号 姓名 实验日期： 实验二 最大子段和、0-1背包问题 一．实验目的 学习最大子段和问题的简单算法，掌握原理，运用C++编程实现。 学习0-1背包问题的简单算法，掌握原理，运用C++编程实现。 二．实验内容 （1）设计最大子段和问题的算法,上机编程实现。 （2）设计0-1背包问题的算法，上机编程实现。 三．实验代码 1 .分治法实现最大子段和程序如下： #includeiostream.h int MaxSum(int a[],int left,int right) { int sum=0; if (left==right) { if (a[left]0) sum=a[left]; else sum=0; } else{ int center=(left+right)/2; int leftsum=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+=a[i]; if(leftss1) s1=lefts; } int s2=0; int rights=0; for(int j=center+1;j=right;j++) { rights+=a[j]; if(rightss2) s2=rights; } sum=s1+s2; if(sumleftsum)sum=leftsum; if(sumrightsum)sum=rightsum; } return sum; } void main() { int n,a[100],m,maxsum; cout分治法求解endl; cout请输入待求的元素数目endl; cinn; cout请输入各元素endl; for(m=1;m=n;m++) cina[m]; maxsum=MaxSum(a,1,n); cout当前序列最大子段和为：maxsumendl; } （2）0-1背包问题程序如下： #includeiostream #includecstdio #includeconio.h #includeiomanip using namespace std; templateclass ty class Knap { public: friend void Init(); friend void Knapsack(); friend void Backtrack(int i); friend float Bound(int i); bool operator(Knapty a)const { if(fla.fl) return true; else return false; } private: ty w; //重量 ty v; //价值 float fl; //单位重量的价值v/w int kk; //记录第几个物品 int flag; //记录是否放入包中 }; templateclass ty void Sort(Knapty *li,int n) { int i,j,k; Knapty minl; for(i=1;in;i++) { minl=li[0]; k=0; for(j=1;j=n-i;j++) { if(minlli[j]) { minl=li[j]; swap(li[j],li[k]); k=j; } } } }