当前位置: 首页> 汽车> 时评 > 1387:搭配购买(buy)

1387:搭配购买(buy)

时间:2025/7/11 14:40:30来源:https://blog.csdn.net/pheatonhb/article/details/139930049 浏览次数: 0次

【解题思路】
       有限钱买物品,要价值最大,每件物品只能买一次,能看出这是一个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;
}

关键字:1387:搭配购买(buy)

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: