并查集：

1.查询（采用了递归的方法）

2.合并、

完整代码模板（联系题目直接套模板）

1.优化前

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100int uset[MAXSIZE];//定义一个足够长的数组
//用下标来表示结点
/*
构造并查集
int size 有多少个节点
*/
void makeSet(int size)
{for (int i = 1; i < size; i++){//各自为各自的代表uset[i] = i;}
}/*
找到元素所在的集合的代表 如果位于同一集合 
*/
int find(int i)
{if (i == uset[i]){return i;}return find(uset[i]);
}void unite(int x, int y) 
{//先找相对应的代表int x = find(x);int y = find(y);if (x == y){return;}uset[x] = y;}

2.优化后

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
/*
因为在特殊情况下 这棵树可能是一个长长的树链 设链的最后一个节点为x
每次执行find 相当于遍历整个链条
只需要把便利过的结点都改成跟的子节点 查询就会快很多
*/int uset[MAXSIZE];//定义一个足够长的数组 每个结点
int rank[MAXSIZE];//树的高度//用下标来表示结点
/*
构造并查集
int size 有多少个节点
*/
void makeSet(int size)
{for (int i = 1; i <= size; i++){//各自为各自的代表uset[i] = i;//树的高度rank[i] = 0;}
}/*
找到元素所在的集合的代表 如果位于同一集合
查找元素在哪个集合
*/
int find(int i)
{if (i == uset[i]){return i;}return uset[i] = find(uset[i]);//在第一次查找的时候 将结点直接连到跟
}void unite(int x, int y)
{//先找相对应的代表int x = find(x);int y = find(y);if (x == y){return;}//判断两棵树的高度 在决定谁为子树if (rank[x] < rank[y]){uset[x] = y;}else{uset[y] = x;if (rank[x] == rank[y]){rank[x]++;}}
}

背包问题：

1.01背包：物品有限，求取最大价值dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])

2.完全背包：物品无限，求最大价值dp[j]=max(dp[j],dp[j-w[i]]+v[i])

3.多重背包：每个物品只能拿指定数目