信息学奥赛一本通 1387：搭配购买(buy) | 洛谷 P1455 搭配购买

【题目链接】

ybt 1387：搭配购买(buy)
洛谷 P1455 搭配购买

【题目考点】

1. 并查集

2. 动态规划：01背包

【解题思路】

有限钱买物品，要价值最大，每件物品只能买一次，能看出这是一个01背包问题。
题目中说：“互相搭配的云要一起买”，并给定了云之间的搭配关系，这就是一种集合关系。这种集合结构可以使用并查集来表示。
互相搭配的云构成一个集合，一个云的集合是一件物品，集合中所有云的价值加和为该物品的价值，集合中所有云的价钱加和为该物品的重量。
因此知道了每件物品的价值和重量，背包大小为这个人拥有的钱数w，用01背包问题的解法即可解决该问题。

【题解代码】

解法1：并查集+01背包

#include
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;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！