算法提高课汇总

算法思路

在有限个云朵中选择总价格不超过额定价格的方案最大价值 — 背包问题.

且如果购买某一搭配中的任意一朵云朵需要将整个搭配全部购买 — 同一
搭配中物品关系不是树形依赖, 而是集合等同.

如果我们将同一搭配中的所有云朵合并为一朵, 问题转变为$01$背包问题.

具体实现

同一搭配的云朵可看作在同一集合, 可用并查集实现. 所有云朵的价格与价值之和与
集合个数属性类似, 是所有元素共有属性, 可以用根节点维护.

实现代码

#include <iostream>

using namespace std;

const int N = 10010, M = 10010;

int n, m, vol;
int w[N], v[N], p[N];
int dp[M];

int find(int x)
{
    if ( p[x] != x )    p[x] = find( p[x] );
    return p[x];
}

int main()
{
    cin >> n >> m >> vol;
    for ( int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

    for ( int i = 1; i <= n; i ++ ) p[i] = i;

    while ( m -- )
    {
        int a, b;
        cin >> a >> b;
        int pa = find(a), pb = find(b);
        if ( pa != pb ) 
        {//在不属于同一集合时合并 否则集合维护属性会增倍
            v[pb] += v[pa];
            w[pb] += w[pa];
            p[pa] = pb;
        }
    }

    //01背包
    for ( int i = 1; i <= n; i ++ )
        if ( p[i] == i ) //合并后的集合由根节点维护
            for ( int j = vol; j >= v[i]; j -- )
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    cout << dp[vol] << endl;

    return 0;
}