计科余定成

用户名：dotcpp0598358

访问量：15771

签　名：

孙蕾，我好喜欢你啊，为了你我要把键盘敲烂!!!

等　　级
排　　名	41
经　　验	13043
参赛次数	1
文章发表	69
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

我是余定成

TA的其他文章

蓝桥杯2016年第七届真题-密码脱落（区间DP）
浏览：208

刻录光盘（c++）
浏览：66

你可能喜欢

C语言程序设计教程（第三版）课后习题12.6 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

优质题解

搭配购买（并查集+01背包）

　　作者: 计科余定成　　　　发表时间：2023-03-06 13:06:59 浏览：103　|　评论：0　

原题链接：搭配购买(buy)

#***前置知识***
### 并查集
 并查集是一种数据结构，主要用于处理一些不交集合的合并及查询问题。它支持两种操作：
```cpp
合并两个集合
查询某个元素所在的集合
```
    并查集使用一个数组来存储一棵树，这棵树的每个节点对应一个元素，节点存储的值就是该元素所在集合的代表元素，所有属于同一集合的元素在这棵树上形成一条路径。具体实现中，使用一个pre数组存储每个元素的父节点，如果一个元素的父节点是它自己，说明它是集合的代表元素
    对于合并操作，我们只需要找到两个元素所在集合的代表元素，然后将其中一个的代表元素的父节点设为另一个集合的代表元素即可。查询操作，只需要不断向上查找每个元素的父节点，直到找到它所在集合的代表元素即可
以下是一个简单的并查集实现代码：
```cpp
const int N = 1e4 + 5;
int pre[N];

void init() {
    for (int i = 1; i <= n; i++) {
        pre[i] = i;
    }
}

int find(int x) {
    if (pre[x] == x) {
        return x;
    } else {
        pre[x] = find(pre[x]);
        return pre[x];
    }
}

void merge(int x, int y) {
    pre[find(x)] = find(y);
}
```
其中，init()函数用于初始化pre数组，find()函数用于查询元素所在集合的代表元素，merge()函数用于合并两个集合。
### 01背包
01 背包是指每个物品只有选或者不选两种状态，不能选取部分，也不能选取多个，这个问题又称为 0/1 背包问题
```cpp
有n个物品，它们有各自的体积和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？
```
使用动态规划求解 01 背包问题，可以定义一个二维数组 dp[i][j]，表示前 i 个物品中选择若干个物品，且总重量不超过 j 的情况下，最大的总价值是多少
*根据题目中所给定的物品重量和价值，可以得到如下状态转移方程：*
![](/image_editor_upload/20230306/20230306124012_62471.png)
由此可以得到如下的 01 背包求解代码：
```cpp
int dp[N][W];
for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= W; j++) {
        dp[i][j] = dp[i-1][j];
        if (j >= w[i]) {
            dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]]+v[i]);
        }
    }
}
```
在01背包问题中，我们需要枚举物品和背包容量。通常情况下，我们是从前往后枚举物品，从小到大枚举背包容量。但是，我们也可以反过来，从后往前枚举物品，从大到小枚举背包容量。这样做的好处是，在计算dp[v]时，dp[v-w[i]]已经被更新过了，因此可以直接使用更新后的dp[v-w[i]]，而不需要额外的空间来存储上一轮的状态
下面是使用倒序枚举进行空间优化的01背包的代码实现：
```cpp
int dp[V+1];
memset(dp, 0, sizeof(dp));
for (int i = n; i >= 1; i--) {
    for (int v = V; v >= w[i]; v--) {
        dp[v] = max(dp[v], dp[v-w[i]] + v[i]);
    }
}
```
 #*解题思路*
大致思路：
```cpp
使用并查集来处理搭配关系，即将云朵按照搭配关系合并为若干个组别，每个组别里的云朵必须一起购买
遍历每个组别，将组别内所有云朵的价值和价格分别累加，得到组别的总价值和总价格
将每个组别视为一个新的物品，使用01背包算法来求解能够购买的最大总价值。注意在01背包中，新物品的价格为组别的总价格，价值为组别的总价值
输出01背包算法的结果即为所求，即能够购买的最大总价值
```
`使用并查集来处理搭配关系`
在本题中，使用并查集来处理云朵的搭配关系。最初，每个云朵都是独立的组别，因此我们需要将相互之间搭配的云朵合并为一个组别。这样，我们就能够根据组别来处理搭配关系，方便计算每个组别的总价值和总价格
`求解每个组别的总价值和总价格`
由于并查集将相互之间搭配的云朵合并为一个组别，因此我们可以通过遍历每个组别来计算每个组别的总价值和总价格。具体而言，我们可以遍历每个云朵，将其所属组别的总价值和总价格分别累加。这样，就可以得到每个组别的总价值和总价格
`将每个组别视为一个新的物品，使用01背包算法来求解能够购买的最大总价值`
接下来，我们将每个组别视为一个新的物品，并使用01背包算法来求解能够购买的最大总价值。在01背包算法中，我们需要考虑总价值不超过背包容量的前提下，如何使总价值最大化。具体而言，我们可以使用dp数组来记录当前状态下能够获得的最大总价值，遍历每个组别，并使用01背包算法更新dp数组的值。最终，dp数组的最后一个元素即为能够购买的最大总价值。
`输出01背包算法的结果`
最后，输出01背包算法的结果即为所求，即能够购买的最大总价值。
# *参考代码*
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
int n, m, w; // n表示云的数量，m表示搭配方案的数量，w表示Joe的钱数
int pre[N]; // 并查集的数组，用于记录每个云所在的集合编号
int W[N], V[N]; // W表示每朵云的价值，V表示每朵云的价格
int dp[N]; // 01背包的dp数组，表示在背包容量为i的情况下，能够获得的最大价值

void init() {
	for (int i = 1; i <= n; i++) {
		pre[i] = i; // 初始化并查集，每朵云最初都是单独的一类
	}
}

int find(int x) { // 并查集的find操作
	if (pre[x] == x ) { // 如果当前云是所在集合的根节点，则返回该根节点
		return x;
	} else { // 否则继续向上寻找根节点，并将路径上所有节点的父节点设置为根节点
		pre[x] = find(pre[x]);
		return pre[x];
	}
}

void merge(int x, int y) { // 并查集的merge操作，将x和y所在的集合合并
	pre[find(x)] = find(y); // 将x所在集合的根节点的父节点设置为y所在集合的根节点
}

int main() {
	// 读入输入
	cin >> n >> m >> w;
	// 并查集初始化，每个元素的根节点为自己
	init();
	// 读入每个云朵的价值和价格
	for (int i = 1; i <= n; i++) {
		cin >> V[i] >> W[i];
	}
	int x, y;
	// 读入每个搭配
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		merge(x, y); // 将x和y所在的集合合并
	}
	// 对于同一个集合中的元素，将它们的价值和价格加起来
	for (int i = 1; i <= n; i++) {
		if (pre[i] != i) {
			V[find(i)] += V[i];
			V[i] = 0;
			W[find(i)] += W[i];
			W[i] = 0;
		}
	}
	// 01背包问题的经典代码实现
	for (int i = 1; i <= n; i++) {
		for (int v = w; v >= V[i]; v--) {
			dp[v] = max(dp[v], dp[v - V[i]] + W[i]);
		}
	}
	// 输出在背包容量为w的情况下所能得到的最大价值
	cout << dp[w];
	return 0;
}

```

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

计科余定成

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题12.6 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

九宫重排（C++代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

搭配购买（并查集+01背包）

评论区

精彩推荐

最小公倍数（C语言代码）

母牛的故事（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

三角形（C++代码）递推

【计算球体积】（C语言代码）

用筛法求之N内的素数。（C语言代码）

母牛的故事（C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言描述——递归算法）

龟兔赛跑预测（C++代码）

P1001 （Java代码）

计科余定成

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题12.6 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

九宫重排 （C++代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

搭配购买（并查集+01背包）

评论区

精彩推荐

最小公倍数 （C语言代码）

母牛的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

三角形 （C++代码）递推

【计算球体积】 （C语言代码）

用筛法求之N内的素数。 （C语言代码）

母牛的故事 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言描述——递归算法）

龟兔赛跑预测 （C++代码）

P1001 （Java代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

九宫重排（C++代码）

　　评论区

最小公倍数（C语言代码）

母牛的故事（C语言代码）

三角形（C++代码）递推

【计算球体积】（C语言代码）

用筛法求之N内的素数。（C语言代码）

母牛的故事（C语言代码）

龟兔赛跑预测（C++代码）