1.背包问题
介绍
有一个容量为C的背包，还有n个物体。现在忽略物体实际几何形状，只要背包的剩余容量大于等于物体体积，那就可以装进背包里。每个物体都有两个属性，即重量w和价值v
问：如何向背包装物体才能使背包中物体的总价值最大？
算法实现
import java.util.Scanner;
class Object{float w;float v;int i;
}
public class Example1 {static int maxnumber=10;static float maxprice;//最大价值public static void main(String[] args) {Object wp[] = new Object[maxnumber];int i,j,n;float C;//背包重量float temp;//交换的中间变量Scanner scanner = new Scanner(System.in);System.out.println("请输入物品种类：");n = scanner.nextInt();System.out.println("请输入背包重量：");C = scanner.nextFloat();System.out.println("请输入物品的序号，重量和价值：\n");for(i=0;i<n;i++) {wp[i].i = scanner.nextInt();wp[i].w = scanner.nextFloat();wp[i].v = scanner.nextFloat();}//输出商品System.out.println("\n输入的物品是：\n");for(i=0;i<n;i++) {System.out.println(wp[i].i);System.out.println(wp[i].w);System.out.println(wp[i].v);}//按商品单位价值排序for(i=0;i<n-1;i++) {for(j=0;j<n-1-i;j++) {if((wp[j].v/wp[j].w) < (wp[j+1].v/wp[j+1].w)) {//交换序号temp=wp[j].i;wp[j].i=wp[j+1].i;wp[j+1].i=(int) temp;//交换重量temp=wp[j].w;wp[j].w=wp[j+1].w;wp[j+1].w=temp;//交换价值temp=wp[j].v;wp[j].v=wp[j+1].v;wp[j+1].v=temp;}}}System.out.println("\n排序后的物品是：\n");for(i=0;i<n;i++) {System.out.println(wp[i].i);System.out.println(wp[i].w);System.out.println(wp[i].v);System.out.println();}maxprice=find(wp,n,C);System.out.println("物品的总价值为：" + maxprice);}private static float find(Object[] wp, int n, float C) {float x[] =new float[maxnumber];maxprice=0;int i;//给解向量赋初值for(i=1;i<=n;i++) {x[i]=(float) 0.0;}i=0;while(wp[i].w <= C) {x[wp[i].i]=1;C=C-wp[i].w;i++;}x[wp[i].i]=C/wp[i].w;//输出解向量for(i=1;i<=n;i++) {System.out.println("x[" + i + "]=" + x[i]);}System.out.println();//计算最大价值for(i=0;i<n;i++) {maxprice=maxprice+wp[i].v*x[wp[i].i];}return maxprice;}}
2.单源最短路径问题—Dijkstra算法
介绍
从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题
注：此算法适用于单源最短路径且每条边的权重必须是正值
算法实现
import java.util.Scanner;
public class Example2 {static int MAX=100;static int INF = 1000;static int graph[][] = new int[MAX][MAX];static int Visited[] = new int[MAX];static int path[] = new int[MAX];static int Distance[] = new int[MAX];public static void main(String[] args) {int m,n,i,k,j;int x,y,w;//一条边的起点，终点，边权Scanner scanner = new Scanner(System.in);System.out.println("请输入顶点数：");m = scanner.nextInt();for(i = 1;i <= m;i++) {//初始化图，所有节点间距离均为无穷大for(j = 1;j <= m;j++) {graph[i][j]=INF;}}System.out.println("请输入边数：");n = scanner.nextInt();for(k = 0;k < n;k++) {//输入边信息x = scanner.nextInt();y = scanner.nextInt();w = scanner.nextInt();graph[x][y] = w;}Dijkstra(1);}//Dijkstra算法求单源最短路径static void Dijkstra(int Begin) {int i,j,k,vertex = 0,MinEdge;//设置所有顶点的上一个顶点为Beginfor(i=1;i<=5;i++) {path[i] = Begin;}//设置源点获取最短路径的上一个节点都为0path[Begin] = 0;//设置所有顶点都未被访问for(i=1;i<=5;i++) {Visited[i] = 0;}//设置源点为永久标号，Visited[i]=1是永久标号，Visited[i]=0是临时标号Visited[Begin] = 1;//设置源点到所有顶点的初始距离for(i=1;i<=5;i++) {Distance[i] = graph[Begin][i];}//源点到自己的初始距离为0Distance[Begin] = 0;for(k=1;k<=5;k++) {//有5个节点，需找4次//获取当前最小的Distance[j],并让该顶点作为永久标号MinEdge=INF;for(j=1;j<=5;j++) {if(Visited[j] == 0 && Distance[j]<MinEdge) {MinEdge=Distance[j];vertex=j;//记录当前具有最短距离的顶点的编号，即获取永久标号的顶点}}//让vertex获取永久标号Visited[vertex] = 1;//获取新标后，更新各临时顶点临时编号的距离for(j=1;j<=5;j++) {if(Visited[j] == 0 && Distance[vertex]+graph[vertex][j]<Distance[j]) {Distance[j] = Distance[vertex] + graph[vertex][j];path[j]=vertex;}}}}}
3.多机调度问题
介绍
有n个作业，计算由m台机器处理的最短时间（n>m）
算法实现
public class Example3 {static int N=7;static int M=3;static int[] s= {0,0,0};//取最大值public static int max(int[] a,int n) {int i,max;max=a[0];for(i=1;i<n;i++) {if(a[i]>max)max=a[i];}return max;}//寻找运行时间最短的机器号static int min(int m) {int mi=0,i;for(i=1;i<m;i++) {if(s[i]<s[mi])mi=i;}return mi;}//机器数大于待分配的作业数static int setwork1(int[] t,int n) {int i;for(i=0;i<n;i++)s[i]=t[i];return max(s,n);}//机器数小于待分配的作业数static int setwork2(int[] t,int n) {int i,mi;//获取作业时间最短的机器号for (i = 0; i < n; i++) {mi=min(M);System.out.println("时间和最小的机器号为:"+ mi +",时间和为:" + s[mi]);s[mi]=s[mi]+t[i];}return max(s,M);}public static void main(String[] args) {int[] time= {16,14,6,5,4,3,2};int maxtime=0;if(M>N)maxtime=setwork1(time, N);else {maxtime=setwork2(time, N);}System.out.println("最多耗时"+maxtime);}
}4.最小生成树（kruskal）克鲁斯卡尔
介绍
一个含有n个顶点的连通图G，若它的一棵带权生成树的各边权值之和最小，则称该生成树为图G的最小生成树，该树包含图的所有顶点，其边的个数为n-1；在生成最小生成树时可以选择不同的边，所以最小生成树不唯一（存在权值相同的边）；但若当图G的各边权值不同，则此时最小生成树是唯一的
克鲁斯卡尔算法适用于求解边稀疏的网
算法实现
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;class Edge{int vex1;int vex2;int weight;
}
public class Example4 {static void kruskal(Edge[] E,int n,int e) {int i,j,m1,m2,sn1,sn2,k,sum=0;int[] vset=new int[n+1];for(i=1;i<=n;i++) {vset[i]=i;}k=1;j=0;while (j<=e-1) {m1=E[j].vex1;m2=E[j].vex2;sn1=vset[m1];sn2=vset[m2];if(sn1!=sn2) {System.out.println("V"+m1+" -> V"+m2+" : "+E[j].weight);sum+=E[j].weight;for (i = 1; i <=n; i++) {if(vset[i]==sn2)vset[i]=sn1;}}j++;}System.out.println(sum);}//快速排序的划分函数public static int fun(Edge[] arr,int low,int high) {int key;Edge lowx=new Edge();lowx=arr[low];key=arr[low].weight;while (low<high) {while (low<high&&arr[high].weight>=key) high--;if(low<high){arr[low++]=arr[high];}while (low<high&&arr[low].weight<=key) low++;if(low<high){arr[high--]=arr[low];}}arr[low]=lowx;return low;}//快速排序函数static void quick_sort(Edge[] arr,int start,int end) {int pos;if(start<end) {pos=fun(arr,start,end);quick_sort(arr, start, pos-1);quick_sort(arr, pos+1, end);}}public static void main(String[] args) {int nume,numn,i;Edge[] E=new Edge[100];System.out.println("输入顶点和边数：");Scanner sc=new Scanner(System.in);numn=sc.nextInt();nume=sc.nextInt();for (i = 0; i < nume; i++) {E[i]=new Edge();E[i].vex1=sc.nextInt();E[i].vex2=sc.nextInt();E[i].weight=sc.nextInt();}quick_sort(E,0,nume-1);for (i = 0; i < nume; i++) {System.out.println(E[i].vex1+" "+E[i].vex2+" "+E[i].weight);}kruskal(E,numn,nume);}
}
5.最小生成树（Prim） 普里姆
介绍
一个含有n个顶点的连通图G，若它的一棵带权生成树的各边权值之和最小，则称该生成树为图G的最小生成树，该树包含图的所有顶点，其边的个数为n-1；在生成最小生成树时可以选择不同的边，所以最小生成树不唯一（存在权值相同的边）；但若当图G的各边权值不同，则此时最小生成树是唯一的
普利姆算法适用于边稠密的网络
算法实现
import java.util.*;
import java.io.*;public class Example5 {static int INF=0x7fffffff;static int MAX=100;public static int Prim(int[][] graph,int n) {int[] lowcost =new int[MAX];int[] mst =new int[MAX];int i,j,min,minid,sum=0;lowcost[1]=0;mst[1]=0;for (i = 2; i<= n; i++) {lowcost[i]= graph[1][i];mst[i]=1;}for (i = 2; i <= n; i++) {min=INF;minid=0;for (j = 2; j <= n; j++) {if(lowcost[j]<min&&lowcost[j]!=0) {min=lowcost[j];minid=j;}}System.out.println("V"+mst[minid]+" -> V"+minid+" : "+min);sum=sum+min;lowcost[minid]=0;for (j = 2; j <= n; j++) {if(graph[minid][j]<lowcost[j]){lowcost[j]=graph[minid][j];mst[j]=minid;}} }return sum;}public static void main(String[] args) {int m,n,i,k,j;int x,y,w;int[][] graph=new int[MAX][MAX];System.out.println("请输入顶点数：");Scanner sc=new Scanner(System.in);m=sc.nextInt();for (i = 1; i <= m; i++) {for (j = 1; j <= m; j++) {graph[i][j]=INF;}}System.out.println("请输入边数：");n=sc.nextInt();for (k = 0; k < n; k++) {x=sc.nextInt();y=sc.nextInt();w=sc.nextInt();graph[x][y]=w;graph[y][x]=w;}//输出邻接矩阵for(i=1;i<=m;i++) {for(j=1;j<=m;j++) {if(graph[i][j]==INF) {System.out.print("A ");}else {System.out.print(graph[i][j]+" ");}}System.out.print("\n");}System.out.println("Total:"+Prim(graph, m));}
}
感谢大家的支持，关注，评论，点赞！
再见！！！
