算法综合实验报告
学号： 1004121206 姓名：林
一、实验内容：
分别用蛮力、动态规划、贪心及分支限界法实现对0-1背包问题的求解，并至少用两个测试用例对所完成的代码进行正确性及效率关系上的验证。
二、程序设计的基本思想、原理和算法描述：
1、蛮力法
1.1数据结构
注：结构体obj用来存放单个物品的价值和重量
typedef struct obj
{
int w;//物品的重量
int v;//物品的价值
};
1.2 函数组成
void subset(int s[][10],int n)：用来生成子集的函数
void judge(int s[][10], obj obj[],int mark[],int n,int c)：判断子集的可行性
int getmax(int mark[],int n,int &flag)：求解问题的最优解
void outputObj(int flag,int s[][10],int n):输出选择物品的情况 1.3 输入/输出设计
本程序通过键盘进行输入、屏幕进行输出。
1.4 符号名说明
符号说明
S[][]存放子集
mark[]记录子集的可行性
n物品的个数
c物品的容量
max记录背包所能产生的最大价值
flag记录能产生最大价值的子集的编号
1.5 算法描述
算法的伪代码描述如下：
输入：背包的容量c,物品的个数n,n个物品的重量 w[n],价值v[n]
输出：装入背包的物品编号以及产生的最大价值
1.初始化最大价值 max=0,结果子集 s=φ;
2.对集合{1,2,......n}的每一个子集T，执行下述操作：
2.1初始化背包的价值 v=0，背包的重量 w=0;
2.2对子集t的每一个元素j
2.2.1 如果w+wj 2.2.2 否则，转步骤2考察下一个子集； 2.3如果max 3.输出子集S中的各元素 2、动态规划法 2.1 数据结构 该程序不涉及任何数据结构 2.2 函数组成 int max(int i,int j);比较并返回两个数中的较大值 int KnapSack (int w[],int v[],int x[],int n,int c);求解背包取得的最大值 2.3 输入/输出设计 本程序通过键盘进行输入、屏幕进行输出。 2.4 符号名说明 符号说明 n物品的个数 c物品的容量 w[] 物品的重量 v[] 物品的价值 x[] 物品的选择情况 V[][] 存放迭代结果 2.5 算法描述 算法的伪代码描述如下： 输入：背包的容量c,物品的个数n,n个物品的重量 w[n],价值v[n] 输出：装入背包的物品标号和背包获得的最大价值 1.初始化二维数组V[][]={0} 2.初始化二维数组的第0行，第0列 2.循环直到i==n 2.1 循环直到j=c 2.1.1 如果背包的容量不足以装入物品i,则装入前i个物品得 到的最大价值和装入前i-1个物品得到的最大价值相等 2.2.2 如果背包的容量可以装入物品i,分别计算装入物品i可 达到的价值量V[i-1][j-w[i]]+v[i],以及不放入物品i可以得到的最大价值V[i-1][j]，取二者中的较大者作为把前i个物品装入容量为j的背包中的最优解 3、贪心法 3.1数据结构 注：结构体用来存放物品的重量、价值、单位价值、物品编号等信息 struct _Object { int Value;//物品价值 int Weight;//物品重量 double AveValue;//物品单位价值 double Num;//物品可以放入的数量 int key;//物品标号 }; 3.2 函数组成 int Partition(_Object r[],int first,int end)；以数组第一个元素为准对数组进行一次划分并返回基准元素的位置坐标 void QuickSort(_Object r[],int first,int end)；快速排序 double knaspsack(int n,int M,_Object object[])；求解背包问题的最优解 3.3 输入/输出设计 本程序通过键盘进行输入、屏幕进行输出。 3.4 符号名说明 符号说明 n物品的个数 c物品的容量 pro[] 物品的重量、价值、单位价值、编号 3.5 算法描述 算法的伪代码描述如下： 输入：背包的容量c,物品的个数n,n个物品的重量 pro[n].Weight,价值pro[n].Value 输出：装入背包的物品标号和背包获得的最大价值 1.计算物品的单位价值并存入pro[n]. 2.将物品按照单位价值递减的顺序进行排序 3.i=0; 4.循环直到（object[i].Weight>c） 4.1 将第i个物品放入背包,object[i].Num=1； 4.2 c-=pro[n].Weight； 4.3 i++； 5.记录最后放入背包的物品的重量： object[i].Num=(double)C/object[i].Weight； 4、分支限界法 4.1数据结构 注：物品结构体，存放物品价值、重量、单位价值、物品编号等信息 struct obj { int v;//物品价值 int w;//物品重量 double avg;//物品单位价值 int id;//物品编号 }; 注：结构体node用来存放节点表节点 struct node { node *parent,//父亲结点指针 *next;//后继结点指针 int level,//节点所处的层 isin,//记录物品是否装入背包，0代表不装,1代表装入 cw,//当前背包已经装入的物品重量 cv;//当前背包已经装入的物品价值 double ub;//结点的上界值 }; 4.2函数组成 int Partition(_Object r[],int first,int end)；以数组第一个元素为准对数组进行一次划分并返回基准元素的位置坐标 void QuickSort(_Object r[],int first,int end)；快速排序 double Upb(int i,int cw,int cv);//计算上界值 node *nnoder(node * parent1,int isin1,double ub1);生成一个新的结点 void addnode(node *node1);//将结点添加到队列中 node *nextnode(); //取下一个结点 void fenzjx();//分支界限法的主要实现函数 void output();//用于输出物品的选择情况及最优解 4.3 输入/输出设计 本程序通过键盘进行输入、屏幕进行输出。 4.4 符号名说明 符号说明 c 背包的容量 n 物品的个数 pro 存放物品信息 avg 物品的单位价值量 opv 背包容量最优解 popv 指向最优解的指针 level 节点的层 cw 当前背包装载量 cv 当前背包价值 ub 节点的上界值 isin 记录当前结点物品是否放入背包 flag 物品原来位置 (4)算法描述 算法的伪代码描述如下： 输入：背包的容量c,物品的个数n,n个物品的信息 pro[n] 输出：装入背包的物品标号和背包获得的最大价值 1.对输入的物品按照单位价值量递减的顺序进行排序 2.初始化问题最优解opv=0,初始化第0层结点，计算上界值 ub=Upb(0,0,0);并设置该结点设为优先级队列的根结点 3.循环直到优先级队列为空 3.1 如果取出当前结点位于第n-1层，则其子结点已是叶子结点， 判断子结点取值情况，若得到的解大于当前问题得到的最优解opv，则重置问题的最优解opv 3.2 如果取出当前结点层 level< n-1 对结点i的每个孩子结点x执行下列操作: 3.2.1 如果结点x可能产生的最优解ub 3.2.2 否则估算该节点x的目标函数值ub,将结点加入队列; 4.将该结点对应的最优值输出，回溯求得最优解的各个分量 三、源程序及注释： 1、蛮力法 #include #include using namespace std; //物品 typedef struct obj { int w; int v; }; //生成子集 void subset(int s[][10],int n) { int i,j,m,k; for(i=0;i { k=i; for(j=n-1;j>=0;j--) { m=k%2; s[i][j]=m; k=k/2; } } } //判断子集可行性 void judge(int s[][10], obj obj[],int mark[],int n,int c) { int i,j,v,w; for(i=0;i { w=0; v=0; for(j=0;j { w+=obj[j].w*s[i][j]; v+=obj[j].v*s[i][j]; } if(w<=c) mark[i]=v; else mark[i]=0; } } //求问题的最优解 int getmax(int mark[],int n,int &flag) { int i,max; max=0; for(i=0;i { if(mark[i]>max) { max=mark[i]; flag=i; } } return max; } //输出选择物品的情况 void outputObj(int flag,int s[][10],int n) { cout<<"装入背包物品的编号为： "; for(int i=0;i { if(s[flag][i]==1) cout< } cout< } int main() { int s[1024][10],mark[1024],n,max,c,flag; obj obj[10]; cout<<"请输入背包的容量："; cin>>c; cout<<"请输入物品的个数："; cin>>n; cout<<"请分别输入物品的重量："; for(int i=0;i { cin>>obj[i].w; } cout<<"请分别输入物品的价值："; for(i=0;i { cin>>obj[i].v; } subset(s,n); judge(s,obj,mark,n,c); max=getmax(mark,n,flag); outputObj(flag,s,n); cout<<"背包可容纳的最大价值为： "< 2、动态规划法 #include using namespace std; //比较并返回两个数中的较大值 int max(int i,int j) { if(i return j; else return i; } //求解背包取得的最大值 int KnapSack (int w[],int v[],int x[],int n,int c) { int i,j,V[105][1005]={0}; for(i=0;i<=n;i++) //初始化第0列 V[i][0]=0; for(j=0;j<=c;j++) //初始化第0行 V[0][j]=0; for(i=1;i<=n;i++) //计算第i行，进行第i次迭代{ for(j=1;j<=c;j++) { if(j V[i][j]=V[i-1][j]; else V[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]); } for(j=c,i=n;i>0;i--) //求装入背包的物品编号{ if(V[i][j]>V[i-1][j]) { x[i]=1; j=j-w[i]; } else x[i]=0; } return V[n][c]; } int main() { int c,n,w[105],v[105],x[105],max;//x[]记录物品的选择情况cout<<"请输入背包的重量："; cin>>c; cout<<"请输入物品的个数："; cin>>n; cout<<"请分别输入物品的重量："; for(int i=1;i<=n;i++) cin>>w[i]; cout<<"请分别输入物品的价值："; for( i=1;i<=n;i++) cin>>v[i]; max=KnapSack(w,v,x,n,c); cout<<"装入背包的物品编号为："; for(i=1;i<=n;i++) { if(x[i]==1) cout< } cout< cout<<"背包可容纳的最大价值为："< return 0; } 3、贪心法 #include #include using namespace std; //物品结构体 struct _Object { int Value;//物品价值 int Weight;//物品重量 double AveValue;//物品单位价值 double Num;//物品可以放入的数量 int key;//物品标号 }; //划分 int Partition(_Object r[],int first,int end){ int i=first,j=end; while(i { while(i j--; if(i { _Object temp=r[i]; r[i]=r[j]; r[j]=temp; i++; } while(i if(i { _Object temp=r[i]; r[i]=r[j]; r[j]=temp; j--; } } return i; } //快速排序 void QuickSort(_Object r[],int first,int end){ int pivot; if(first pivot=Partition(r,first,end); QuickSort(r,first,pivot-1); QuickSort(r,pivot+1,end); } } double knaspsack(int n,int M,_Object object[]) //n为物品个数，M 为背包容量 { int i; int C=M; double maxValue=0; for(i=0;object[i].Weight { object[i].Num=1;//初始化放入背包的物品为0 maxValue+=object[i].Value; C=C-object[i].Weight; } object[i].Num=(double)C/object[i].Weight; maxValue+=object[i].Num*object[i].Value; return maxValue; } int main() { int n,c; _Object pro[1001]; cout<<"背包的容量： "; cin>>c; cout<<"请输入物品的个数："; cin>>n; cout<<"请分别输入物品的重量和价值："; for(int i=0;i { cin>>pro[i].Weight>>pro[i].Value; pro[i].AveValue=(double)pro[i].Value/pro[i].Weight; pro[i].Num=0; pro[i].key=i; } QuickSort(pro,0,n-1); double maxValue=knaspsack(n,c,pro); cout<<"背包的可容纳的最大价值为："; printf("%.2f",maxValue); cout< int k; cout<<"各个物品装入背包的重量分别为："; for(k=0;k { for(int j=0;j { if(pro[j].key==k) //找到原来顺序的物品编号 cout< } } cout< return 0; } 4、分支限界法 #include #include #include #include #include using namespace std; //物品结构体 struct obj { int v;//物品价值 int w;//物品重量 double avg;//物品单位价值 int id;//物品编号 }; //节点结构体 struct node { node *parent,//父亲结点指针 *next;//后继结点指针 int level,//节点所处的层 isin,//记录物品是否装入背包，0代表不装,1代表装入 cw,//当前背包已经装入的物品重量 cv;//当前背包已经装入的物品价值 double ub;//结点的上界值 }; //划分 int Partition(obj r[],int first,int end){ int i=first,j=end; while(i { while(i j--; if(i { obj temp=r[i]; r[i]=r[j]; r[j]=temp; i++; } while(i i++; if(i { obj temp=r[i]; r[i]=r[j]; r[j]=temp; j--; } } return i; } //快速排序 void QuickSort(obj r[],int first,int end){ int pivot; if(first pivot=Partition(r,first,end); QuickSort(r,first,pivot-1); QuickSort(r,pivot+1,end); } } class fzjx{ private: node *front,//队首指针 *first,//根节点指针 *popv;//解结点指针 double opv;//背包可产生的最大价值 obj *pro;//物品 int n,//物品个数 c;//背包容量 public: fzjx(obj *pro1,int w1,int n1 ); ~fzjx(); int *flag; double Upb(int i,int cw,int cv);//计算上界值 node *nnoder(node * parent1,int isin1,double ub1); void addnode(node *node1);//将结点添加到队列中 node *nextnode(); //取下一个结点 void fenzjx(); void output(); }; fzjx::fzjx(obj *pro1,int c1,int n1 ) { int i; n=n1;c=c1; pro=new obj [n]; flag=new int[n]; for(i=0;i { pro[i].w=pro1[i].w; pro[i].v=pro1[i].v; pro[i].id=pro1[i].id; pro[i].avg=pro1[i].avg; flag[i]=i; } front=new node[1]; front->next=NULL; opv=0; popv=new node[1]; popv=NULL; QuickSort(pro,0,n-1); } fzjx::~fzjx() { delete[]first; delete[]front; delete[]popv; delete[]pro; } double fzjx::Upb(int i,int cw,int cv) { int cleft=c-cw; double v=(double)cv; if (i v+=1.0*pro[i].avg*cleft; return v; } 实验三、0-1背包问题（贪心算法） 实验代码： #include printf("物品总数为：7\n"); printf("物品重量和价值分别为：\n"); printf("\n重量价值\n"); for (i=1;i<=n;i++) printf("%d %d \n",w[i],v[i]); int m=15; int array[8][100]={0}; Knapsack(v,w,x,m,7,array); printf("背包能装的最大价值为: %d\n",array[1][m]); printf("贪心算法的解为: "); for(i=1;i<=n;i++) { if(i==1) printf("%d",x[i]); else printf(" %d",x[i]); } printf("\n"); return 0; } 测试截图为： 《算法分析与设计》 课程实验 专业年级：信息与计算科学 学生学号： 学生姓名： 实验题目：用贪婪法求解背包问题 指导老师： 实验时间：20xx年xx月x日 一、实验内容 用贪婪法求解背包问题 要求：用非递归实现 二、实验步骤 2.1、理解算法思想和问题要求； 2.2、写出每个操作的算法 非递归算法： greedbag() { int N; int c; int[] w; int[] v; Scanner scan=new Scanner(System.in); System.out.print("输入背包的容量:"); c=scan.nextInt(); System.out.print("输入物品的数量:"); N=scan.nextInt(); System.out.print("分别输入物品的价值:"); v=new int[N]; for(int i=0;i 分支限界法求解背包问题 /*此程序实现，分支限界法求解背包问题，分支限界法是根据上界=当前背包的价值+背包 剩余载重* （剩余物品最大价值/质量）*/ 分支r 10 I 分S： 104 1.200060' 6 2.i/eeoe #i nclude #include 贪心算法的应用 课程名称：算法设计与分析 院系：计算机科学与信息工程学院 学生姓名：**** 学号：********** 专业班级：********************************** 指导教师：****** 201312-27 贪心算法的应用 摘要：顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。贪心算法求问题一般具有两个重要性质：贪心选择性质和最优子结构性质。所谓贪心选择性是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法主要区别。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 背包问题是一个经典的问题，我们可以采用多种算法去求解0/1背包问题，比如动态规划法、分支限界法、贪心算法、回溯法。在这里我们采用贪心法解决这个问题。 关键词：贪心法背包问题最优化 目录 第1章绪论 (3) 1.1 贪心算法的背景知识 (3) 1.2 贪心算法的前景意义 (3) 第2章贪心算法的理论知识 (4) 2.1 问题的模式 (4) 2.2 贪心算法的一般性描述 (4) 第3章背包问题 (5) 3.1 问题描述 (5) 3.2 问题分析 (5) 3.3算法设计 (5) 3.4 测试结果与分析 (10) 第4章结论 (12) 参考文献 (13) 附件 (13) 算法分析与设计实验报告 第 4 次实验 } 附录：完整代码 #include 算法综合实验报告 学号： 1004121206 姓名：林 一、实验内容： 分别用蛮力、动态规划、贪心及分支限界法实现对0-1背包问题的求解，并至少用两个测试用例对所完成的代码进行正确性及效率关系上的验证。 二、程序设计的基本思想、原理和算法描述： 1、蛮力法 1.1数据结构 注：结构体obj用来存放单个物品的价值和重量 typedef struct obj { int w;//物品的重量 int v;//物品的价值 }; 1.2 函数组成 void subset(int s[][10],int n)：用来生成子集的函数 void judge(int s[][10], obj obj[],int mark[],int n,int c)：判断子集的可行性 int getmax(int mark[],int n,int &flag)：求解问题的最优解 void outputObj(int flag,int s[][10],int n):输出选择物品的情况 1.3 输入/输出设计 本程序通过键盘进行输入、屏幕进行输出。 1.4 符号名说明 符号说明 S[][]存放子集 mark[]记录子集的可行性 n物品的个数 c物品的容量 max记录背包所能产生的最大价值 flag记录能产生最大价值的子集的编号 1.5 算法描述 算法的伪代码描述如下： 输入：背包的容量c,物品的个数n,n个物品的重量 w[n],价值v[n] 输出：装入背包的物品编号以及产生的最大价值 1.初始化最大价值 max=0,结果子集 s=φ; 2.对集合{1,2,......n}的每一个子集T，执行下述操作： 2.1初始化背包的价值 v=0，背包的重量 w=0; 2.2对子集t的每一个元素j 2.2.1 如果w+wj 背包问题贪心法 实验报告 学院：计算机科学与技术学院班级：**** 学号：**** 姓名：**** 一、实验目的 1）以背包问题为例，掌握贪心法的基本设计策略。 2）熟练掌握各种贪心策略情况下的背包问题的算法并实现；其中：量度标准分别取：效益增量P 、物品重量w 、P/w 比值； 3) 分析实验结果来验证理解贪心法中目标函数设计的重要性。 二、问题基本思想描述 (1)贪心法的基本思路 从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。 该算法存在问题： 1. 不能保证求得的最后解是最佳的； 2. 不能用来求最大或最小解问题； 3. 只能求满足某些约束条件的可行解的范围。 （2）背包问题的描述 已知有n 种物品和一个可容纳M 重量的背包，每种物品i 的重量为i w 。假定将物品i 的一部分 i x 放入背包就会得到 i i x p 的效益，这里， 1 0≤≤i x , >i p 。 显然，由于背包容量是M ，因此，要求所有选中要装入背包的物品总重量不得超过M.。如果这n 件物品的总重量不超过M ，则把所有物品装入背包自然获得最大效益。现需解决的问题是，在这些物品重量的和大于M 的情况下，该如何装包，使得得到更大的效益值。由以上叙述，可将这个问题形式表述如下： 极 大 化目标函数 ∑≤≤n i i x p 1i 约束条件 M x w n i i ≤∑ ≤≤1i n i w p x i i i ≤≤>>≤≤1,0,0,10 （3）用贪心策略求解背包问题 首先需确定最优的量度标准。这里考虑三种策略： 0-1背包问题 计科1班朱润华2012040732 方法1:回溯法 一、回溯法描述： 用回溯法解问题时， 应明确定义问题的解空间。 问题的解空间至少包含问题的一个 (最 优)解。对于0-1背包问题，解空间由长度为 n 的0-1向量组成。该解空间包含对变量的所 有 0-1 赋值。例如 n=3 时，解空间为： {(0, 0, 0), (0, 1, 0), (0, 0, 1) , (1, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0), (1 , 1, 1) 然后可将解空间组织成树或图的形式， 0-1背包则可用完全二叉树表示其解空间给定 n 种物品和一背包。物品i 的重量是wi ,其价 值为vi ,背包的容量为 C 。问：应如何选择装入背包的物品，使得装入背包中物品的总价值 最大？ 形式化描述：给定 c >0, wi >0, vi >0 , 1 w i < n.要求找一 n 元向量(x1,x2,…,xn,), xi € {0,1}, ? 刀wi xi w c,且刀vi xi 达最大.即一个特殊的整数规划问题。 二、回溯法步骤思想描述： 0-1背包问题是子集选取问题。0-1背包问题的解空间可以用子集树表示。在搜索解空 间树时，只要其 左儿子节点是一个可行节点， 搜索就进入左子树。当右子树中有可能含有最 优解时，才进入右子树搜索。否则，将右子树剪去。设 r 是当前剩余物品价值总和， cp 是 当前价值；bestp 是当前最优价值。当 cp+r<=bestp 时，可剪去右子树。计算右子树上界的 更好的方法是将剩余物品依次按其单位价值排序， 然后依次装入物品， 直至装不下时，再装 入物品一部分而装满背包。 例如：对于 0-1 背包问题的一个实例，n=4,c=7,p=[9,10,7,4],w=[3,5,2,1] 品的单位重量价值分别为[3,2,3,5,4]。以物品单位重量价值的递减序装入物品。 品4,然后装入物品3和1.装入这3个物品后，剩余的背包容量为1,只能装 由此得一个解为[1,0.2,1,1]，其相应价值为22。尽管这不是一个可行解，但可以证明其价 值是最优值的上界。因此，对于这个实例，最优值不超过 在实现时，由 Bound 计算当前节点处的上界。类 Knap 的数据成员记录解空间树中的节 点信息，以减少参数传递调用所需要的栈空间。 在解空间树的当前扩展节点处， 仅要进入右 子树时才计算上界 Bound,以判断是否可将右子树剪去。进入左子树时不需要计算上界，因 为上界预期父节点的上界相同。 三、回溯法实现代码： #i nclude "stdafx.h" #in clude #include<> #define N 100 typedef struct bao{ int num; float w; float v; }; typedef struct avg{ int num; ( float val; float w; float v; }; struct bao b[N]; struct avg d[N]; int n; float c; ^ void Sort() { int i,j,k; struct avg temp[N]; for(i=0;i float x[N],sum = 0; for(i=0;i 算法设计与分析实验报告 题目：贪心算法背包问题 专业：JA V A技术xx——xxx班 学号： 姓名： 指导老师： 实验三：贪心算法背包问题 一、实验目的与要求 1、掌握背包问题的算法 2、初步掌握贪心算法 二、实验题： 问题描述：与0-1背包问题相似，给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为c。与0-1背包问题不同的是，在选择物品i装入背包时，背包问题的解决可以选择物品i的一部分，而不一定要全部装入背包，1< i < n。 三、实验代码 import java.awt.*; import java.awt.event.*; import javax.swing.*; public class er extends JFrame { private static final long serialVersionUID = -1508220487443708466L; private static final int width = 360;// 面板的宽度 private static final int height = 300;// 面板的高度 public int M; public int[] w; public int[] p; public int length; er() { // 初始Frame参数设置 this.setTitle("贪心算法"); setDefaultCloseOperation(EXIT_ON_CLOSE); setSize(width, height); Container c = getContentPane(); c.setLayout(new BoxLayout(c, BoxLayout.Y_AXIS)); setLocation(350, 150); // 声明一些字体样式 Font topF1 = new Font("宋体", Font.BOLD, 28); Font black15 = new Font("宋体", Font.PLAIN, 20); Font bold10 = new Font("宋体", Font.BOLD, 15); // 声明工具栏及属性设置 JPanel barPanel = new JPanel(); JMenuBar topBar = new JMenuBar(); topBar.setLocation(1, 1); barPanel.add(topBar); // 面板1和顶部标签属性设置 JPanel p1 = new JPanel(); JLabel topLabel = new JLabel("背包问题"); 算法设计与分析期末论文 题目用贪心法求解“0-1背包问题”专业计算机科学与技术 班级09计算机一班 学号0936021 姓名黄帅 日期2011年12月28日 一、0-1背包问题的算法设计策略分析 1.引言 对于计算机科学来说，算法的概念是至关重要的，例如，在一个大型软件系统的开发中，设计出有效的算法将起决定性的作用。算法是解决问题的一种方法或一个过程。程序是算法用某种设计语言具体实现描。计算机的普及极大的改变了人们的生活。目前，各行业、各领域都广泛采用了计算机信息技术，并由此产生出开发各种应用软件的需求。为了以最小的成本、最快的速度、最好的质量开发出适合各种应用需求的软件，必须遵循软件工程的原则。设计一个高效的程序不仅需要编程小技巧，更需要合理的数据组织和清晰高效的素算法，这正是计算机科学领域数据结构与算法设计所研究的主要内容。 2. 算法复杂性分析的方法介绍 算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N 、I 和A 表示算法要解问题的规模、算法的输入和算法本身，而且用C 表示复杂性，那么，应该有C=F(N,I,A)。一般把时间复杂性和空间复杂性分开，并分别用T 和S 来表示，则有： T=T(N,I)和S=S(N,I) 。（通常，让A 隐含在复杂性函数名当中 最坏情况下的时间复杂性： 最好情况下的时间复杂性： 平均情况下的时间复杂性： 其中DN 是规模为N 的合法输入的集合；I*是DN 中使T(N, I*)达到Tmax(N)的合法输入； 是中使T(N, )达到Tmin(N)的合法输入；而P(I)是在算法的应用中出现输入I 的概率。 算法复杂性在渐近意义下的阶： 渐近意义下的记号：O 、Ω、θ、o 设f(N)和g(N)是定义在正数集上的正函数。 O 的定义：如果存在正的常数C 和自然数N0，使得当N ≥N0时有f(N)≤Cg(N)，则称函数f(N)当N 充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N))。即f(N)的阶不高于g(N)的阶。 根据O 的定义，容易证明它有如下运算规则： (1)O(f)+O(g)=O(max(f,g))； (2)O(f)+O(g)=O(f+g)； (3)O(f)O(g)=O(fg)； (4)如果g(N)=O(f(N))，则O(f)+O(g)=O(f)； (5)O(Cf(N))=O(f(N))，其中C 是一个正的常数； ∑∈= N D I I N T I P (N)T ),()(avg ∑∑∈==N D I k i i i I N e t I P ),()(1),(min min I N T (N)T N D I ∈=),(min 1I N e t k i i i D I N ∑=∈=)~,(1I N e t k i i i ∑==)~,(I N T =),(max max I N T (N)T N D I ∈=),(max 1I N e t k i i i D I N ∑=∈=),(*1I N e t k i i i ∑==) ,(*I N T = 分支限界法——01背包问题 12软工 028 胡梦颖 一、问题描述 0-1背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。 二、问题分析 分支限界法类似于回溯法，也是在问题的解空间上搜索问题解的算法。一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。由于求解目标不同，导致分支限界法与回溯法对解空间的搜索方式也不相同。回溯法以深度优先的方式搜索解空间，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间。分支限界法的搜索策略是，在扩展结点处，先生成其所有的儿子结点(分支)，然后再从当前的活结点表中选择下一扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值(限界)，并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。这种方式称为分支限界法。人们已经用分支限界法解决了大量离散最优化的问题。 三．源代码 #include 算法设计与分析大作业 班级：电子154 姓名：吴志勇 学号： 1049731503279 任课老师：李瑞芳 日期： 2015.12.25 算法设计与分析课程论文 0-1背包问题的算法设计策略对比与分析 0 引言 对于计算机科学来说，算法的概念是至关重要的。在一个大型软件系统的开发中，设计出有效的算法将起到决定性的作用。通俗的讲，算法是解决问题的一种方法。也因此，《算法分析与设计》成为计算科学的核心问题之一，也是计算机科学与技术专业本科及研究生的一门重要的专业基础课。算法分析与设计是计算机软件开发人员必修课，软件的效率和稳定性取决于软件中所采用的算法；对于一般程序员和计算机专业学生，学习算法设计与分析课程，可以开阔编程思路，编写出优质程序。通过老师的解析，培养我们怎样分析算法的“好”于“坏”，怎样设计算法，并以广泛用于计算机科学中的算法为例，对种类不同难度的算法设计进行系统的介绍与比较。本课程将培养学生严格的设计与分析算法的思维方式，改变随意拼凑算法的习惯。本课程要求具备离散数学、程序设计语言、数据结构等先行课课程的知识。 1 算法复杂性分析的方法介绍 算法复杂性的高低体现在运行该算法所需要的计算机资源的多少上，所需的资源越多，该算法的复杂性越高；反之，所需资源越少，该算法的复杂性越低。对计算机资源，最重要的是时间与空间（即存储器）资源。因此，算法的复杂性有时间复杂性T(n)与空间复杂性S(n)之分。 算法复杂性是算法运行所需要的计算机资源的量，这个量应集中反映算法的效率，并从运行该算法的实际计算机中抽象出来，换句话说，这个量应该只依赖要解决的问题规模‘算法的输入和算法本身的函数。用C表示复杂性，N,I和A表示问题的规模、算法的输入和算法本身规模，则有如下表达式： C=F(N,I,A) T=F(N，I,A) S=F(N，I,A) 其中F(N,I,A)是一个三元函数。通常A隐含在复杂性函数名当中，因此表达式中一般不写A。 即：C=F(N,I) T=F(N,I) S=F(N,I) 算法复杂性中时间与空间复杂性算法相似，所以以下算法复杂性主要以时间复杂性为例： 算法的时间复杂性一般分为三种情况：最坏情况、最好情况和平均情况。下面描述算法复杂性时都是用的简化的复杂性算法分析，引入了渐近意义的记号O,Ω，θ，和o。 O表示渐近上界Ω表示渐近下界： θ表示同阶即：f(n)= O(g(n))且 f(n)= Ω（g(n)） 2 常见的算法分析设计策略介绍 2.1 递归与分治策略 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。 由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。 分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。 递归算法举例： 共11页第1页 实验四“0-1”背包问题 一、实验目的与要求 熟悉C/C++语言的集成开发环境； 通过本实验加深对贪心算法、动态规划算法的理解。 二、实验内容: 掌握贪心算法、动态规划算法的概念和基本思想，分析并掌握“0-1”背包问题的求解方法，并分析其优缺点。 三、实验题 1.“0-1”背包问题的贪心算法 2.“0-1”背包问题的动态规划算法 说明：背包实例采用教材P132习题六的6-1中的描述。要求每种的算法都给出最大收益和最优解。 设有背包问题实例n=7，M=15,，(w0,w1,。。。w6)=（2,3,5,7,1,4,1），物品装入背包的收益为：（p0，p1，。。。，p6）=（10,5,15,7,6,18,3）。求这一实例的最优解和最大收益。 四、实验步骤 理解算法思想和问题要求； 编程实现题目要求； 上机输入和调试自己所编的程序； 验证分析实验结果； 整理出实验报告。 五、实验程序 // 贪心法求解 #include 实验四用分支限界法实现0-1背包问题 一.实验目的 1.熟悉分支限界法的基本原理。 2.通过本次实验加深对分支限界法的理解。 二.实验内容及要求 内容：?给定n种物品和一个背包。物品i的重量是w,其价值为v，背包容量为c。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？ 要求：使用优先队列式分支限界法算法编程，求解0-1背包问题 三.程序列表 #inelude stack 贪心算法详解 贪心算法思想： 顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。 贪心算法的基本要素： 1.贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。 2. 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的 最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 贪心算法的基本思路： 从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。 该算法存在问题： 1. 不能保证求得的最后解是最佳的； 2. 不能用来求最大或最小解问题； 3. 只能求满足某些约束条件的可行解的范围。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解； 用背包问题来介绍贪心算法： 背包问题：有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要 求尽可能让装入背包中的物品总价值最大，但不能超过总容量。 算法设计与分析实验报告 实验名称贪心算法实现背包问题评分 实验日期年月日指导教师 姓名专业班级学号 一.实验要求 1. 优化问题 有n个输入，而它的解就由这n个输入满足某些事先给定的约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。可行解一般来说是不唯一的。那些使目标函数取极值(极大或极小)的可行解，称为最优解。 2.贪心法求优化问题 算法思想：在贪心算法中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪心决策的依据称为贪心准则（greedy criterion）。 3.一般方法 1）根据题意，选取一种量度标准。 2）按这种量度标准对这n个输入排序 3）依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。 procedure GREEDY(A，n) /*贪心法一般控制流程*/ //A(1：n)包含n个输入// solutions←φ //将解向量solution初始化为空／ for i←1 to n do x←SELECT(A) if FEASIBLE(solution，x) then solutions←UNION(solution，x) endif repeat return(solution) end GREEDY 4. 实现典型的贪心算法的编程与上机实验，验证算法的时间复杂性函数。 二.实验内容 1. 编程实现背包问题贪心算法。通过具体算法理解如何通过局部最优实现全局最优， 并验证算法的时间复杂性。 2.输入5个的图的邻接矩阵，程序加入统计prim算法访问图的节点数和边数的语句。 3.将统计数与复杂性函数所计算比较次数比较，用表格列出比较结果，给出文字分析。 三.程序算法 1.背包问题的贪心算法 procedure KNAPSACK(P，W，M，X，n) //P(1：n)和W(1；n)分别含有按 P(i)/W(i)≥P(i+1)/W(i+1)排序的n件物品的效益值 和重量。M是背包的容量大小，而x(1：n)是解向量 real P(1：n)，W(1：n)，X(1：n)，M，cu； integer i，n； X←0 //将解向量初始化为零 cu←M //cu是背包剩余容量 for i←1 to n do if W(i)>cu then exit endif X(i) ←1 cu←cu-W(i) repeat if i≤n then X(i) ←cu/ W(i) endif end GREEDY-KNAPSACK procedure prim(G,) status←“unseen” // T为空 status[1]←“tree node” // 将1放入T for each edge(1,w) do status[w]←“fringe” // 找到T的邻接点 dad[w] ←1; //w通过1与T建立联系 dist[w] ←weight(1,w) //w到T的距离 repeat while status[t]≠“tree node” do pick a fringe u with min dist[w] // 选取到T最近的节点 status[u]←“tree node” for each edge(u,w) do 修改w和T的关系 repeat repeat 2.Prim算法 实验五应用贪心算法求解背包问题 学院：计算机科学与技术专业：计算机科学与技术 学号：班级：姓名： 、 实验内容： 背包问题指的是：有一个承重为W的背包和n个物品，它们各自的重量和价值分别是n ，假设W w i和v i（1 i n）w i 1i，求这些物品中最有价值的一个子集。如果每次选择某一个物品的时候，只能全部拿走，则这一问题称为离散（0-1）背包问题；如果每次可以拿走某一物品的任意一部分，则这一问题称为连续背包问题。 二、算法思想： 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 三、实验过程： #in elude { float p; // 物品效益 float w; // 物品重量 float X; // 物品该放的数量 int flag; // 物品编号 };// 物品信息结构体 void Insertionsort(goodinfo goods[],int n)// 插入排序，按pi/wi 价值收益进行排序，一般教材上按冒泡排序 { int j,i; for(j=2;j<=n;j++) { goods[0]=goods[j]; i=j-1; while (goods[0].p>goods[i].p) { } goods[i+1]=goods[0]; } }// 按物品效益，重量比值做升序排列goods[i+1]=goods[i]; i--; void bag(goodinfo goods[],float M,int n) { float cu; int i,j;贪心算法0-1背包问题(算法实验代码)
算法设计实验_贪心算法背包问题
分支限界法求解背包问题
【精选】贪心算法的应用
背包问题(贪心算法)
蛮力法、动归、贪心、分支限界法解01背包问题剖析
背包问题贪心法
回溯法和分支限界法解决0-1背包题
C语言版贪心算法背包问题
贪心算法背包问题
用贪心法求解0-1背包问题
0-1背包问题(分支限界法)
0-1背包问题的算法设计策略对比与讲解
背包问题-贪心法和动态规划法求解
实验4用分支限界法实现0-1背包问题
贪心算法详解分析
贪心算法实现背包问题算法设计与分析实验报告
c应用贪心算法求解背包问题
相关主题
文本预览