1.五大算法思想:
①分治思想
快排、分组排序、归并排序、二分查找
②贪心算法/贪婪算法
大的问题 归纳成小问题 然后迭代
1)A星寻路算法
能且只能做当前看来最优的选择 如此反复 试图得到最终最优解
缺陷:
1. 并非一定能得到整体最优解
2. 每一步都是局部最优2)最值思想:
3)背包问题:
有一个体积为V的背包
有N种物品 体积和价值各不相同
求价值最高的组合方式4)迪杰斯卡拉:求最短路径
③ 动态规划
④ 动态回溯--->递归 n皇后问题
⑤ 分支定界2.贪心算法的基本思想
3.贪心算法的常见应用:
①背包问题(货物装载问题)
②最短路径问题--->dijkstra算法
③哈夫曼编码
④短作业调度问题
整个算法的流程的关键--->两个内部的循环
①第一个for:访问集合内的点都被标记为了flag=1,
所以我们需要在剩下的点中找到起点到当前点距离最短的(贪心),
并记录min=dist[j],将这个点标记,k表示获取到的其下标
②第二个for:在上一个for完成扩充点的基础上
(扩充完点之后,最新扩充的这个点的dist from 起点 to 新点 就不会再改变了!!!)
就要开始遍历剩下的点,寻找是否有更优的路径。
关键比较对象:min+map.matrix[k][j]与dist[j]
其中min就是dist[k]=起点到k点最短的距离,加上matrix[k][j](即k到j的距离) 就是表示起点到j这个点的距离。
- #include
- #include
- #include
- #define NO 0xFFFFFF //不连通
- #define MAX 10 //不能直接定义太大数组
- //简单描述一下图
- typedef struct graph
- {
- char vexs[MAX]; //顶点数组
- int vexnum; //顶点数
- int arcnum; //边数
- int matrix[MAX][MAX]; //权值数组
- }GRAPH,*LPGRAPH;
- void DijKstra(GRAPH map, int in, int dist[])
- {
- int i = 0;
- int flag[MAX]; //成功获取路径(进入了扩充的顶点范围内)的标记
- //求出当前节点到其他节点距离
- for (int i = 0; i < map.vexnum; i++)
- {
- flag[i] = 0;
- dist[i] = map.matrix[in][i]; //当前节点到其他节点距离遍历第一行权值数组
- }
- flag[in] = 1;
- dist[in] = 0;
- int min;
- int k=0;
- int j;
- //2.扩充顶点
- //数组存储顶点从下标0存储
- for (i = 1; i < map.vexnum; i++) //i=1本质是扩充第二个顶点
- {
- min = NO; //不连通的值
- /*第一个循环:是用来找到目前未扩充的且入口到其点距离最小的那个点*/
- for (j = 1; j < map.vexnum; j++)
- {
- if (flag[j] == 0 && dist[j] < min)
- {
- min = dist[j];
- k = j; //连通的状态
- }
- }
- flag[k] = 1;//找到后,将其标记为1--->代表已经进入扩充的名单内了。
- /*第二个循环:判断剩下没进入+有更加适合的路径的点,更新dist距离数组*/
- for (j = 1; j < map.vexnum; j++)
- {
- if (flag[j] == 0 && (min + map.matrix[k][j]) < dist[j])
- {
- dist[j] = min + map.matrix[k][j];
- }
- }
- }
- printf("\n");
- for (int i = 1; i < map.vexnum; i++)
- {
- printf("最短路径:(%c,%c)=%d\n", map.vexs[in], map.vexs[i], dist[i]);
- }
- //如何求出最短路径 经过那些节点
-
- }
- int main()
- {
- GRAPH map = { {'1','2','3','4','5'},5,7,
- {
- {NO,10,NO,30,100},
- {NO,NO,50,NO,NO},
- {NO,NO,NO,NO,10},
- {NO,NO,20,NO,60},
- {NO,NO,NO,NO,NO}
- }
- };
- int in = 0; //'1'这个顶点进来,找到其他顶点距离
- int dist[MAX];
- DijKstra(map, in, dist);
- return 0;
- }
Q:求最大值?
主体:
- #include
- #define NUM 5
- int arr[NUM][NUM] = { 0 };
- //临时数组
- int maxArr[NUM][NUM] = { 0 };
- int count = 0;
- //返回 a b 中大的那一个
- int Max(int a, int b)
- {
- return ((a > b) ? a : b);
- }
- //初始化数组
- void initArr();
- //获取最大路径
- int getMax(int i, int j);
- int main()
- {
- initArr();
-
- int num = getMax(0, 0);
-
- printf("num:%d,count:%d\n", num,count);
-
- while (1);
- return 0;
- }
- //初始化数组
- void initArr()
- {
- arr[0][0] = 9;
- arr[1][0] = 4; arr[1][1] = 7;
- arr[2][0] = 5; arr[2][1] = 3; arr[2][2] = 1;
- arr[3][0] = 2; arr[3][1] = 4; arr[3][2] = 4; arr[3][3] = 1;
- arr[4][0] = 7; arr[4][1] = 5; arr[4][2] = 3; arr[4][3] = 2; arr[4][4] = 4;
-
- for (int i = 0; i < NUM; i++)
- {
- for (int j = 0; j < NUM; j++)
- {
- maxArr[i][j] = -1;
- }
- }
- }
核心函数getMax的实现与逐步优化 :
①版本一:递归暴力求解。
(会有重复搜的地方---->左支向下搜索,完毕后,进行右支搜索,会有重复的搜索部分)
//获取最大路径 int getMax(int i, int j) { //step1 :递归方式 每一步都计算 爆破法 if (NUM == i) return arr[i][j];//越界 循环结束 int n = getMax(i + 1, j); int m = getMax(i + 1, j + 1); count++;//统计计算次数 return arr[i][j] + Max(n, m); }②版本二:优化上述问题,左支自底向上求解出的max将其存储起来,等到第二次搜索时,若已经标记过就不用再搜索了,直接用就可以。
//获取最大路径 int getMax(int i, int j) { //step2 :递归方式 有一些没有意义的递归 要省略 存储之前递归计算出来的结果 直接用 而不是每次都递归计算出来再用 if (maxArr[i][j] != -1) return maxArr[i][j]; /*省略就体现在这一步, 因为标记只会标记较优解(下面走过的路, 已经额外存储过了, 比如左边搜过了, 进行一系列的标记max, 当右边搜到相同子分支的时候, 就没有必要搜了(自下而上将其求解出最优解了, 没有必要再去搜了))*/ count++; if (NUM == i) { maxArr[i][j] = arr[i][j]; } else { int n = getMax(i + 1, j); int m = getMax(i + 1, j + 1); maxArr[i][j] = arr[i][j] + Max(n, m); } return maxArr[i][j]; }③版本三:递归写法--->优化成循环写法(减少函数调用的开销
//获取最大路径 int getMax(int i, int j) { //step3 :循环方式 直接从下往上加 //先给最下面一层赋值 for (int i = 0; i < NUM; i++) maxArr[NUM - 1][i] = arr[NUM - 1][i]; //循环 一层层 加 一层层往上赋值 for (int i = NUM - 2; i >= 0; i--) {//从下往上 for (int j = 0; j <= i; j++) { maxArr[i][j] = arr[i][j] + Max(maxArr[i + 1][j], maxArr[i + 1][j + 1]); } } //返回maxArr[0][0] return maxArr[0][0]; }④版本四:由于要额外开辟一个maxArr用来存储搜索过的最优解,十分耗费空间的,
于是可以用覆盖的方式,进行空间层面的优化。
//获取最大路径 int getMax(int i, int j) { //step4 :循环方式 直接从下往上加 空间方面只用一行(采用覆盖的方式优化空间) int temp[NUM]; //先给最下面一层赋值 for (int i = 0; i < NUM; i++) temp[i] = arr[NUM - 1][i]; //循环 一层层 加 一层层往上赋值 for (int i = NUM - 2; i >= 0; i--) {//从下往上 for (int j = 0; j <= i; j++) { temp[j] = arr[i][j] + Max(temp[j], temp[j + 1]); } } //返回 return temp[0]; }
- #include
- /*
- 有N样物品 N:5
- 容量为V的背包 V:20
- A B C D E
- w: 3 5 6 7 9
- c: 2 8 7 4 1
- 32
- */
- #define V 20
- #define N 5
- struct Items
- {
- int w;//体积weight
- int c;//价值
- };
- Items wp[N] = { { 3, 2}, { 5,8 }, { 6, 7}, { 7,4 }, { 9,1 } };
- //返回 a b 中大的那一个
- int Max(int a, int b)
- {
- return ((a > b) ? a : b);
- }
- int main()
- {
- int temp[100] = { 0 };//存储各种体积对应的价值
- for (int i = 0; i < N; i++)
- {//种类搭配
- for (int j = wp[i].w; j <= V; j++)
- {//j表示体积
- temp[j] = Max(temp[j], temp[j - wp[i].w] + wp[i].c);
- printf("i:%d,j:%d,temp[%d-%d]:%d,temp[%d]:%d\n",
- i, j, j, wp[i].w, temp[j - wp[i].w],j,temp[j]);
- }
- }
- printf("max:%d\n", temp[V]);
- return 0;
- }
①j++表示什么?
当i=0的时候,表示只可以装第一个物品, 所以这边temp 的变化是这样的(temp[20]=12是因为6个w=3的物品,价值为2,故6*2),当i=1的时候,表示可以在原来的基础上搭配第二个物品->依次更新temp,一直到i=4完成最后一次的更新。
②temp[j-wp[i].w]+wp[i].c
表示如果在原来temp数组的方案商空出i=1的这个item的体积对应的价值再加上i=1的item的价值,去和对应temp[j]价值进行比较--->取较大的temp值进行存储即可。例:当i=2,temp[14]=18表示当上限体积给到14的时候,仅有0和1两种物品,最优价值可以达到18。