上传算法图解相关内容 · CTCSU/AlgorithmGraphExample@5a0f920 · GitHub
Skip to content

Commit 5a0f920

Browse files
CTCSUCTCSU
committed
上传算法图解相关内容
1 parent bc9c752 commit 5a0f920

10 files changed

Lines changed: 241 additions & 91 deletions

‎src/main/java/BreadthFirstSearch.java‎

Lines changed: 2 additions & 0 deletions

‎src/main/java/Dijkstra.java‎

Lines changed: 32 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,22 @@
1+
import SupportData.GraphSearchUtil;
2+
13
import java.util.ArrayList;
24
import java.util.Arrays;
35
import java.util.List;
46

7+
/**
8+
* 迪杰斯特拉算法
9+
* 对于带权值的有向无环图,迪杰斯特拉算法能够计算出从给定的起点到终点最短的路径
10+
* 做法如下:
11+
* 维护一个包含从起点到所有节点的权值的数据组;
12+
* 依次从这个数据组中取出权值最小的节点作为基准,遍历这个基准节点所有相连通的节点,比较起点通过这个节点到另外的节点(起点到这个节点的权值+这个节点到其他节点的权值)和当前数据组中起点到另外节点的值的大小;
13+
* 如果通过这个节点到另外节点的权值更小的话,那么就更新数据组中的值.
14+
* 依次更新,直到终点是数据组中未做基准点而且权值最小的点.
15+
* 原理:因为是有向图并且无环,作为基准的点,当时的权值都是起点到这些节点最小的时候.
16+
* 书中解释:找出途中最便宜的节点,并且确保没有到该节点的更便宜的路径.
17+
*
18+
*
19+
*/
520
public class Dijkstra implements AlgorithmInGraph {
621

722
public void showAlgorithm() {
@@ -23,10 +38,25 @@ public void showAlgorithm() {
2338
graph[3][4] = 1;
2439

2540
GraphSearchUtil.printGraph(graph);
26-
List<Integer> nodes = doDijkstra(graph,0,4);
27-
System.out.println(Arrays.toString(nodes.toArray()));
41+
List<Integer> nodes = doDijkstra(graph,1,0);
42+
if(nodes != null) {
43+
System.out.println(Arrays.toString(nodes.toArray()));
44+
}else{
45+
System.out.println("当前条件起点到终点不可达");
46+
}
47+
2848
}
2949

50+
51+
/**
52+
* 传入一个图的数据的二维数组,图需要是有向图,并且不能有环的存在
53+
* 传入起始节点和终结节点
54+
* 返回节点的list,就是从起点到终点算出来权值最短的路径的节点
55+
* @param graph
56+
* @param start
57+
* @param end
58+
* @return
59+
*/
3060
private List<Integer> doDijkstra(int [][] graph,int start,int end) {
3161

3262
int length = graph.length;

‎src/main/java/KnapsackProblem.java‎

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
import java.util.ArrayList;
2+
import java.util.Arrays;
3+
4+
/**
5+
* 贪心算法解决背包问题
6+
* 贪心算法原理,当前问题的最优解就是全局问题的最优解,所以找到当前最优解就好;
7+
* 对于背包问题而言,因为物品都是可以分割的,
8+
* 所以每次选择一定量当前还存在的单位价值最大的物品就好了
9+
*
10+
*/
11+
public class KnapsackProblem implements AlgorithmInGraph{
12+
13+
14+
public void showAlgorithm() {
15+
int [] weighs = {5,9,3,7,10,6};
16+
int [] value ={10,20,5,3,30,5};
17+
System.out.println("物品重量为:"+Arrays.toString(weighs));
18+
System.out.println("物品价值为:"+ Arrays.toString(value));
19+
20+
int maxWeight = 16;
21+
22+
System.out.println("背包容量为"+maxWeight);
23+
double maxValue = doKnapsack(weighs,value,maxWeight);
24+
System.out.println("这个背包能装入物品的最大价值为"+maxValue);
25+
}
26+
27+
public double doKnapsack(int [] weighs,int [] value,int maxWeight ){
28+
for(int i = 0;i < weighs.length - 1;i++){
29+
for(int j = 0; j < weighs.length - i - 1 ;j++ ){
30+
if(weighs[j] /(double)value[j] > weighs[j+1]/(double)value[j+1] ){
31+
swap(weighs,j,j+1);
32+
swap(value,j,j+1);
33+
}
34+
}
35+
}
36+
37+
double currentWeight = 0;
38+
int i = 0;
39+
double maxValue = 0;
40+
while(i<weighs.length){
41+
if(currentWeight + weighs[i] < maxWeight){
42+
currentWeight += weighs[i];
43+
maxValue += value[i];
44+
45+
}else {
46+
maxValue += value[i] * (maxWeight - currentWeight) / weighs[i];
47+
break;
48+
}
49+
i++;
50+
}
51+
return maxValue;
52+
}
53+
54+
public void swap(int [] array,int left,int right){
55+
int temp = array[left];
56+
array[left] = array[right];
57+
array[right] = temp;
58+
}
59+
}

‎src/main/java/QuickSort.java‎

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -17,6 +17,7 @@ public void showAlgorithm() {
1717
for(int i = 0;i<10;i++){
1818
array[i] = random.nextInt(100);
1919
}
20+
array = new int[]{58, 67, 58, 72, 1, 52, 91, 80, 42, 58};
2021
System.out.println("排序前生成的数组的顺序是: \t" + Arrays.toString(array));
2122
sort(array);
2223
System.out.println("排序后的数组的顺序是: \t" + Arrays.toString(array));
@@ -35,10 +36,11 @@ private void quickSort(int [] array,int start,int end){
3536
int right = end;
3637
int value = array[start];
3738
while(left < right){
38-
while(array[right] > value && left < right)
39+
//这里为什么是大于等于?因为在右边的大于等于标准值就可以了.如果不加等号,那么相等的值就没有办法
40+
while(array[right] >= value && left < right)
3941
right--;
4042
array[left] = array[right];
41-
while(array[left] < value && left < right)
43+
while(array[left] <= value && left < right)
4244
left++;
4345
array[right] = array[left];
4446
}

‎src/main/java/SupportData/Graph.java‎

Lines changed: 0 additions & 83 deletions
This file was deleted.

src/main/java/GraphSearchUtil.java renamed to src/main/java/SupportData/GraphSearchUtil.java

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,5 @@
1+
package SupportData;
2+
13
import java.util.Arrays;
24
import java.util.Random;
35

‎src/main/java/SupportData/TestUtil.java‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
package SupportData;
2+
3+
import java.io.File;
4+
import java.io.IOException;
5+
import java.net.URL;
6+
import java.net.URLDecoder;
7+
import java.util.ArrayList;
8+
import java.util.Enumeration;
9+
import java.util.List;
10+
11+
public class TestUtil {
12+
13+
public static List<Class<?>> getAllClassesByPackageName(String packageName){
14+
List<Class<?>> classes = new ArrayList<Class<?>>();
15+
Enumeration<URL> dirs;
16+
try {
17+
dirs = Thread.currentThread().getContextClassLoader().getResources(packageName);
18+
while(dirs.hasMoreElements()){
19+
URL url = dirs.nextElement();
20+
String filePath = URLDecoder.decode(url.getFile(),"UTF-8");
21+
classes.addAll(getAllClassesByFilePath(filePath));
22+
}
23+
24+
} catch (IOException e) {
25+
e.printStackTrace();
26+
}
27+
return classes;
28+
29+
}
30+
31+
private static List<Class<?>> getAllClassesByFilePath(String filePath){
32+
List<Class<?>> result = new ArrayList<Class<?>>();
33+
34+
File file = new File(filePath);
35+
36+
File [] files = file.listFiles();
37+
38+
for(File childFile:files){
39+
if(childFile.isDirectory()){
40+
continue;
41+
}
42+
try {
43+
String fileName = childFile.getName();
44+
result.add(Class.forName(fileName.substring(0,fileName.length()-6)));
45+
} catch (ClassNotFoundException e) {
46+
e.printStackTrace();
47+
}
48+
}
49+
return result;
50+
51+
}
52+
53+
}

‎src/main/java/ZeroOneKnapsack.java‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
import SupportData.GraphSearchUtil;
2+
3+
import java.util.Arrays;
4+
5+
/**
6+
* 01背包：
7+
* 动态规划问题的核心是当前问题的最优解包含在小规模的最优解中，或者说大规模问题可以由小规模问题推导出来，也就是状态转移；
8+
* 具体到0，1背包；状态转移为：对于第i件物品，在背包容量限定为weight的情况下，其最大价值在放这件物品与不放这件物品之间选择一个：
9+
* a：如果放的话，那么价值为当前背包容量减去该物品重量后能放置物品的最高价值与当前物品的价值累加；就是数组中a[i-1][weight-weighs[i]]
10+
* b: 如果不放的话，那么价值就应该是当前背包容量下不考虑这个物品，也就是上个物品在该背包容量的最大价值：也就是数组中a[i-1][weight]
11+
* a与b的最大值就是当前规模的最优值
12+
*/
13+
public class ZeroOneKnapsack implements AlgorithmInGraph {
14+
15+
public void showAlgorithm() {
16+
int [] weighs = {5,9,1
17+
,7,10,6,7};
18+
19+
int [] value ={10,20,5,3,30,5,5};
20+
int maxWeight = 16;
21+
22+
int maxValue = doZeroOneKnapsack(weighs,value,maxWeight);
23+
System.out.println("物品重量为:"+ Arrays.toString(weighs));
24+
System.out.println("物品价值为:"+ Arrays.toString(value));
25+
System.out.println("背包容量为"+maxWeight);
26+
27+
System.out.println("这个背包能装入物品的最大价值为"+maxValue);
28+
}
29+
30+
public int doZeroOneKnapsack(int [] weighs ,int [] value,int maxWeight){
31+
maxWeight = maxWeight + 1;
32+
int [][] currentState = new int [weighs.length][maxWeight];
33+
int maxResult = 0;
34+
for(int i=0;i<weighs.length;i++){
35+
for(int j=0;j<maxWeight;j++){
36+
//初始化
37+
if(i==0){
38+
if(j >= weighs[0]){
39+
currentState[i][j] = value[0];
40+
}
41+
}else if(j >= weighs[i] ){
42+
if(currentState[i-1][j-weighs[i]]+value[i] > currentState[i-1][j]){
43+
currentState[i][j] = currentState[i-1][j-weighs[i]]+value[i];
44+
}else{
45+
currentState[i][j] = currentState[i-1][j];
46+
}
47+
}
48+
else{
49+
currentState[i][j] = currentState[i-1][j];
50+
}
51+
if(maxResult < currentState[i][j]){
52+
maxResult = currentState[i][j];
53+
}
54+
}
55+
}
56+
57+
GraphSearchUtil.printGraph(currentState);
58+
return maxResult;
59+
}
60+
}

‎src/test/java/AlgorithmInGraphTest.java‎

Lines changed: 21 additions & 2 deletions

0 commit comments

Comments
 (0)