目录

并查集

01背包

---

并查集

用于解决：

1.将两个集合合并
2.询问两个集合是否再一个集合中

原理：每个集合用一颗数标识，树根的编号就是集合的编号，每个节点存储父节点p【x】是x的父节点
 

 

题目 ：合并集合

一共有 nn 个数，编号是 1∼n1∼n，最开始每个数各自在一个集合中。

现在要进行 mm 个操作，操作共有两种：

1. M a b，将编号为 aa 和 bb 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
2. Q a b，询问编号为 aa 和 bb 的两个数是否在同一个集合中；

输入格式

第一行输入整数 nn 和 mm。

接下来 mm 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。

输出格式

对于每个询问指令 Q a b，都要输出一个结果，如果 aa 和 bb 在同一集合内，则输出 Yes，否则输出 No。

每个结果占一行。

代码 

#include<iostream>
using namespace std;
int p[100001];
 
int find(int x)//寻找根节点+路径压缩
{
    
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
 
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    p[i]=i;
    
    string s;
    int a;int b;
    while(m--)
    {
        cin>>s>>a>>b;
        
        if(s=="M") p[find(a)] = find(b);
        
        else 
        {
            if(find(a)==find(b)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    
    
    return 0;
}

01背包

背包解决的问题是：
有一个容量为v的背包 共有n个物品 每个物品所占空间为 w 价值为val 求背包所能装下的物品的总价值最大为多少。

01背包 就是 每个物品只有一个 也就是每个物品只能去一次

状态：满足条件的目前背包装的物品

状态转移方程：
f[i][j] =max(f[i-1][j],f[i-1][j-w[i]]+val[i]);
f[i][j] i代表第i个物品，j代表前i个物品所占有总的体积 f值为目前前i个物品的总价值
f[i][j] 这个状态由它前一个物品f[i-1][] 加上对于第i个物品的判断 第i个物品可以选择加入背包和不加入背包，不满足加入背包的条件则f[i][j]的值就是它前一个f[i-1][j]; 如果加入背包，加入后的背包体积为j 则加入前的 选择方式为f[i-1][j-w[i]]

滚动数组的优化：
由于枚举到第i个物品时，用到的数据只有i-1行，其前面的都用不到
所以空间优化一下
f[j]=max(f[j],f[j-w[i]]+val[i]);
f[j] j代表前i个物品占用的空间 ，f的值时背包内所有物品的价值
只用i从1到n循环覆盖就实现了从 1个物品 到i个物品的更新

因为时01背包所以 j从后往前保证每个物品只被枚举一次

 题目

有 NN 件物品和一个容量是 VV 的背包。每件物品只能使用一次。

第 ii 件物品的体积是 vivi，价值是 wiwi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，N，VN，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 NN 行，每行两个整数 vi,wivi,wi，用空格隔开，分别表示第 ii 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值

 代码

#include<iostream>
using namespace std;
 
 int f[1000];
 
int main()
{
    int t,n;
    cin>>n>>t;
    
    for(int i=1;i<=n;i++)
    {
        int c,val;
        cin>>c>>val;
       for(int j=t;j>=c;j--)
       {
         f[i]=max(f[i],f[i-c]+val);
       }
       
    }
       
   cout<<f[t];
 
 
return 0;
}