算法设计与分析实验报告
四、实验过程设计（算法设计过程）
(1)用数组b[0:n-1]记录以a[i],0<=i max{b[k]}?1 据此将计算b[i]长度。序列a的最长递增子序列的长度为0?k?ia[k]?a[i]转化为i个规模更小的子问题。 (2)转化成一般背包问题即可，具体算法过程与背包问题大同小异 五、实验结果分析 (2)六、实验体会 时间复杂度为O(nb) 学会了用动态规划的想法来解决背包问题，为了给出合适的测试数据也是捣鼓了好久，让我知道算法思想重要，他的测试和实现也很重要，这次课题的限制降低很多让我们有更多的思考空间，提升了想象力。 七、附录：（源代码） (1)int pia() { } int maxL(int n) 2015-2016学年 第一学期 int i,j,k; for(i=1,b[0];i return maxL(n); for(j=0,k=0;j b[i]=k-1; 算法设计与分析实验报告 { } (2)import java.util.Scanner; public class beibao{ static void knapsack(int n,float c,float[] v,float[]w,float []x) { Sort(n,v,w); int i; for(i=1;i<=n;i++) x[i]=0; for(i=1;i<=n;i++) { if(w[i]>c) break; x[i]=1; c-=w[i]; } if(i<=n) x[i]=c/w[i]; } int i,j; for(i=0;i Scanner scan =new Scanner(System.in); System.out.println(\输背包中物品的个数：\); int n=scan.nextInt(); System.out.println(\输入背包的容量：\); float c=scan.nextFloat(); float [] v=new float[n+1]; for(int i=0,temp=0;i static void Sort(int n, float[] v, float[] w) { if(v[i]/w[i] public static void main(String[] args) { float [] w=new float[n+1]; float [] x=new float[n+1]; for(int i=1;i<=n;i++) { System.out.println(\输入第\+i+\的重量\); w[i]=scan.nextFloat(); System.out.println(\输入第\+i+\的价值\); v[i]=scan.nextFloat(); 2015-2016学年 第一学期 算法设计与分析实验报告 } knapsack(n,c,v,w,x); System.out.println(\一般背包问题的解为：\); for(int i=1;i<=n;i++) System.out.print(x[i]+\); } } 实验三 贪心算法 一、实验目的 1．加深学生对动态规划算法设计方法的基本思想、基本步骤、基本方法的理解与掌握； 2．提高学生利用课堂所学知识解决实际问题的能力； 3．提高学生综合应用所学知识解决实际问题的能力。 二、实验内容 1、单源最短路径 2、一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，之处应在哪些加油站停靠加油，使沿途加油次数最少。并证明算法能产生一个最优解。 三、实验要求 （1）用贪心算法思想求解最优问题； （2）再选择自己熟悉的程序设计语言实现所有算法； （3）分析所设计的算法的时间/空间复杂性。 四、实验过程设计（算法设计过程） 1、设置顶点几何S并不断地做贪心选择来扩充这个集合一个顶点属于s当且仅当源到该顶点的最短路径长度已知，u为g中某个顶点，把从源到u且中间只经过s中顶点的路径称为从源到u的特殊路径，并用dist记录当前每个顶点所对应的最短特殊路径长度。一旦s包含了所有v的点，dist就记录了从源到所有其他顶点之间的最短路径长度。 2、设加油次数为k，每个加油站间距离为a[i]；i=0，1，2，3……n 1.始点到终点的距离小于Ｎ，则加油次数k=0； 2.始点到终点的距离大于N， ① 加油站间的距离相等，即ａ[i]=a[j]=L=N，则加油次数最少k=n； ② 加油站间的距离相等，即ａ[i]=a[j]=L>N，则不可能到达终点； ③ 加油站间的距离相等，即ａ[i]=a[j]=L ④ 加油站间的距离不相等，即ａ[i]！=a[j]，则加油次数k通过下面的算法求解。 五、实验结果分析 2015-2016学年 第一学期 算法设计与分析实验报告 (1) 时间复杂度为O(n) 2(2)时间复杂度为O(n) 六、实验体会 通过这次实验让我感受到独立思考写算法的乐趣，尤其是加油站问题，其中遇到很多困难，但是在和同学们的讨论下，我茅塞顿开，感受到了贪心算法是如何进行他的贪心行为，大大提升了我的编程能力和对贪心算法的理解。 七、附录：（源代码） (1)public class Dijkstra { static int MAX_SIZE=6; public static void dijkstra(int v,float[][]a,float[]dist,int[]prev){ int n=dist.length-1; if(v<1||v>n)return; boolean []s=new boolean[n+1]; for(int i=1;i<=n;i++) { dist[i]=a[v][i]; s[i]=false; if(dist[i]==Float.MAX_VALUE) prev[i]=0; else prev[i]=v; } dist[v]=0;s[v]=true; for(int i=1;i for(int j=1;j<=n;j++) 2015-2016学年 第一学期 算法设计与分析实验报告 if((!s[j])&&(dist[j] temp=dist[j]; } s[u]=true; for(int j=1;j<=n;j++) if((!s[j])&&(a[u][j] public static void main(String args[]){ float a[][]=new float[MAX_SIZE][MAX_SIZE]; float[]dist=new float[MAX_SIZE]; int []prev=new int[MAX_SIZE]; for(int i=0;i<6;i++) for(int j=0;j<6;j++) a[i][j]=Float.MAX_VALUE; a[1][2]=10; a[1][4]=30;a[1][5]=100; a[2][3]=50; a[3][5]=10; a[4][3]=20; a[4][5]=60; int v=1;//假设从顶点1处出发 dijkstra(v,a,dist,prev); System.out.println(\从1出发到2、3、4、5的最短路径依次是:\ for(int j=2;j<6;j++){ System.out.println(dist[j]); } int z=prev[5],y=prev[z],x=prev[y]; System.out.println(\从1到5最短路径经过的点为：\ System.out.print(x+\ (2)public class qiyou { public static void greedy(int []v,int n,int N){ //定义每个加油站的距离存进数组v，定义加满油可以开n公里 //定义要跑N公里 int s=v.length; int k=0; //初始化经过加油站的数量k int load=0;//初始化走过的长度 if(N System.out.println(\不需要加油\ } for(int i=0;i System.out.println(\还没到加油站就没油了！\ } } for(int i=0;i 2015-2016学年 第一学期