算法设计与分析实验报告学院：信息学院专业：物联网1101姓名：黄振亮学号：20113379 2013年11月目录作业1 0-1背包问题的动态规划算法 (7)1.1算法应用背景 (3)1.2算法原理 (3)1.3算法描述 (4)1.4程序实现及程序截图 (4)1.4.1程序源码 (4)1.4.2程序截图 (5)1.5学习或程序调试心得 (6)作业2 0-1背包问题的回溯算法 (7)2.1算法应用背景 (3)2.2算法原理 (3)2.3算法描述 (4)2.4程序实现及程序截图 (4)2.4.1程序源码 (4)2.4.2程序截图 (5)2.5学习或程序调试心得 (6)作业3循环赛日程表的分治算法 (7)3.1算法应用背景 (3)3.2算法原理 (3)3.3算法描述 (4)3.4程序实现及程序截图 (4)3.4.1程序源码 (4)3.4.2程序截图 (5)3.5学习或程序调试心得 (6)作业4活动安排的贪心算法 (7)4.1算法应用背景 (3)4.2算法原理 (3)4.3算法描述 (4)4.4程序实现及程序截图 (4)4.4.1程序源码 (4)4.4.2程序截图 (5)4.5学习或程序调试心得 (6)作业1 0-1背包问题的动态规划算法1.1算法应用背景从计算复杂性来看,背包问题是一个NP难解问题。
半个世纪以来,该问题一直是算法与复杂性研究的热点之一。
另外,背包问题在信息加密、预算控制、项目选择、材料切割、货物装载、网络信息安全等应用中具有重要的价值。
如果能够解决这个问题那么则具有很高的经济价值和决策价值，在上述领域可以获得最大的价值。
本文从动态规划角度给出一种解决背包问题的算法。
1.2算法原理1.2.1、问题描述：给定n种物品和一背包。
物品i的重量是wi，其价值为vi，背包的容量为C。
问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,), xi ∈{0,1}, ∋∑ wi xi≤c,且∑ vi xi达最大.即一个特殊的整数规划问题。
1.2.2、最优性原理：设(y1,y2,…,yn)是 (3.4.1)的一个最优解.则(y2,…,yn)是下面相应子问题的一个最优解:证明:使用反证法。
若不然,设(z2,z3,…,zn)是上述子问题的一个最优解,而(y2,y3,…,yn)不是它的最优解。
显然有∑vizi > ∑viyi (i=2,…,n)且 w1y1+ ∑wizi<= c因此 v1y1+ ∑vizi (i=2,…,n) > ∑ viyi, (i=1,…,n)说明(y1,z2, z3,…,zn)是(3.4.1)0-1背包问题的一个更优解,导出(y1,y2,…,yn)不是背包问题的最优解,矛盾。
1.2.3、递推关系：设所给0-1背包问题的子问题的最优值为m(i ，j)，即m(i ，j)是背包容量为j ，可选择物品为i ，i+1，…，n 时0-1背包问题的最优值。
由0-1背包问题的最优子结构性质，可以建立计算m(i ，j)的递归式:注:(3.4.3)式此时背包容量为j ，可选择物品为i 。
此时在对xi 作出决策之后,问题处于两种状态之一:(1)背包剩余容量是j,没产生任何效益； (2)剩余容量j-wi,效益值增长了vi ；1.3算法描述int m[100][100];//前i 个物品装入容量为j 的背包中获得的最大价值 int s;//获得的最大价值 int w[15];//物品的重量 int v[15];//物品的价值int x[15];//物品的选取状态，1表示被选中 0表示未选中 int n,i;int c;//背包最大容量int max(int a,int b)//获得最大值 int min(int a,int b)//获得最小值void KnapSack(int n,int w[],int v[],int c)//背包问题主算法先为m[n][j] 初始化初值然后根据递归方程式进行穷举递归直到 m[1][c]， m[1][c] 即为所获得的最大价值。
void Traceback(int n,int w[],int x[],int c)//回溯算法，依次标注被选中的物品通过一个循环过程检验装入第i 个物品与装入i+1个物品的价值如果相同，则x[i]=0。
1.4程序实现及程序截图 1.4.1程序源码#include<iostream> using namespace std;int m[100][100];//前i 个物品装入容量为j 的背包中获得的最大价值 int max(int a,int b) {if(a>=b) return a; else return b; }int min(int a,int b){if(a>=b)return b;else return a;}void KnapSack(int n,int w[],int v[],int c){int i,j;int jMax=min(w[n]-1,c);for(j=0;j<=jMax;j++) m[n][j]=0;for(j=w[n];j<=c;j++) m[n][j]=v[n];for(i=n-1;i>1;i--){jMax=min(w[i]-1,c);for(j=0;j<=jMax;j++) m[i][j]=m[i+1][j];for(j=w[i];j<c;j++)m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);}m[1][c]=m[2][c];if(c>=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}void Traceback(int n,int w[],int x[],int c){int i;for(i=1;i<n;i++)if(m[i][c]==m[i+1][c]) x[i]=0;else{x[i]=1;c-=w[i];}x[n]=(m[n][c])?1:0;}int main() {int s;//获得的最大价值int w[15];//物品的重量int v[15];//物品的价值int x[15];//物品的选取状态int n,i;int c;//背包最大容量cout <<"请输入背包的最大容量:"<< endl;cin>>c;cout<<"输入物品数:\n"<<endl;cin>>n;cout<<"请分别输入物品的重量:"<<endl;for(i=1;i<=n;i++)cin>>w[i];cout<<"请分别输入物品的价值:"<<endl;for(i=1;i<=n;i++)cin>>v[i];KnapSack(n,w,v,c);Traceback(n,w,x,c);s=m[1][c];cout<<"最大物品价值为:"<<endl;cout<<s<<endl;cout<<"选中的物品为："<<endl;for(i=1;i<=n;i++)cout<<x[i];return 0;｝1.4.2程序截图1.5学习或程序调试心得利用动态规划求解0-1背包问题的复杂度为0(min{nc,2n}。
动态规划主要是求解最优决策序列，当最优决策序列中包含最优决策子序列时，可建立动态规划递归方程，它可以帮助高效地解决问题。
作业2 0-1背包问题的回溯算法1.1算法应用背景背包问题是一个在运筹学领域里常见的典型NP-C 难题，也是算法设计分析中的经典问题，对该问题的求解方法的研究无论是在理论上,还是在实践中都具有重要意义。
对这个问题的求解已经研究出了不少的经典方法，对该问题的探索和应用研究一直在进行。
在先进理论指导下，求解0-1背包问题具有科学、高效、经济、灵活、方便等显著特点。
那么要解决背包问题，首要的前提就是设计出好的算法，想求得背包问题的解，就要先设计出算法,本文采用回溯法对背包问题给出具体算法设计和实现过程。
如何将背包问题应用于实际问题中，有针对性地设计适合求解实际0-1背包问题的算法，并很好地解决实际问题，是计算机工作者不断思索、研究的一个领域。
2.2算法原理 2.2.1 问题描述问题的一般描述是：旅行者背包登山，背包的最大承重为M ，现有n 个物品可供选择装入背包，第i 个物品莺量为wi ，价值为pi ，假定物品i 的一部分xi(0≤xi ≤1)放人背包，获得价值为xipi ，由于背包最大承重为M ，要求装入物品总质量不过超过M ，问旅行者应该如何选择物品装入背包，使得装入物品的价值总和达到最大值。
背包问题的数学描述如下：要求找到一个n 元向量(x1，x2…xn)，在满足约束条件：⎪⎩⎪⎨⎧≤≤≤∑10i i i x Mw x 情况下，使得目标函数p x ii ∑max ，其中，1≤i ≤n ；M>0；wi>0；pi>0。
满足约束条件的任何向量都是一个可行解，而使得目标函数达到最大的那个可行解则为最优解。
给定n 种物品和1个背包。
物品i 的重量是wi ，其价值为pi ，背包的容量为M 。
问应如何装入背包中的物品，使得装人背包中物品的总价值最大？在选择装人背包的物品时，对每种物品i 只有两种选择，即装入背包、不装入背包。
不能将物品i 装人背包多次，也不能只装入部分的物品i 。
该问题称为0-1背包问题。
0-1背包问题的符号化表示是，给定M>0， w i >0， pi >0，1≤i ≤n ，要求找到一个n 元0-1向量向量(x1，x2…xn)， X i =0 或1 , 1≤i ≤n, 使得M wx ii≤∑ ，而且p x ii∑达到最大。
2.2.2算法分析1、问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。
问题的解空间应到少包含问题的一个（最优）解。
2、回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。
这个开始结点就成为一个活结点，同时也成为当前的扩展结点。
在当前的扩展结点处，搜索向纵深方向移至一个新结点。
这个新结点就成为一个新的活结点，并成为当前扩展结点。