【解题思路】
有限钱买物品,要价值最大,每件物品只能买一次,能看出这是一个01背包问题。
题目中说:“互相搭配的云要一起买”,并给定了云之间的搭配关系,这就是一种集合关系。这种集合结构可以使用并查集来表示。
互相搭配的云构成一个集合,一个云的集合是一件物品,集合中所有云的价值加和为该物品的价值,集合中所有云的价钱加和为该物品的重量。
因此知道了每件物品的价值和重量,背包大小为这个人拥有的钱数w,用01背包问题的解法即可解决该问题。
【题解代码】
#include<bits/stdc++.h>
using namespace std;
#define N 10005
int n, m, wn;
int fa[N], c[N], d[N];//c[i]:以i为根结点的集合的总价钱 d[i]:i为根结点的集合的总价值
int v[N], w[N], an, dp[N];//背包问题 v:价值 w:重量 dp[j]:前i个物品装入大小为j的背包的最大价值
void init()
{for(int i = 1; i <= n; ++i)fa[i] = i;
}
int find(int x)
{return fa[x] == x ? x : (fa[x] = find(fa[x]));
}
void merge(int i, int j)
{int x = find(i), y = find(j);if(x != y){fa[x] = y;c[y] += c[x];d[y] += d[x];}
}
int main()
{int f, t;cin >> n >> m >> wn;init();//并查集初始化 for(int i = 1; i <= n; ++i)cin >> c[i] >> d[i];for(int i = 1; i <= m; ++i)//根据输入的关系构成集合 {cin >> f >> t;merge(f, t);}for(int i = 1; i <= n; ++i)//寻找根结点,将每个集合的价钱和价值提取出来 {if(fa[i] == i){v[++an] = d[i];w[an] = c[i];}}for(int i = 1; i <= an; ++i)//01背包问题:有an个商品,第i商品价值v[i],重量w[i],背包大小wn。 for(int j = wn; j >= w[i]; --j)dp[j] = max(dp[j], dp[j-w[i]] + v[i]);cout << dp[wn];return 0;
}