[Leaf] [P1064] 金明的预算方案

luogu-p1064-金明的预算方案">Luogu-P1064 金明的预算方案

1. 题面梗概

中译中: 0/1 背包，但物品之间有依赖关系：附件不能单独买，必须买了它对应的那个主件才能买。一个主件最多两个附件。

2. 逻辑推导

本题的难点在于“依赖”。普通背包是独立决策，但这题你买附件的前置条件是主件。

我们考虑暴力：能不能直接 0/1 背包？很显然是不行的，如果主件没选，附件的转移就是非法的，这不符合 DP 的无后效性。

怎么切入呢？注意到题目给了一个很关键的限制条件：每个主件最多只有两个附件。

既然附件这么少，我们直接枚举所有的购买策略不就行了吗？

分析后我们发现，对于主件 $A$ 和附件 $a,b$。有且仅有 5 种决策。

不买。$A$。$A+a$。$A+b$。$A+a+b$。

而这 5 种决策是互斥的，那么就可以转化为一个分组背包来解决。

3. 代码实现

▶

AcCode

#include<bits/stdc++.h>
using namespace std;

const int maxn = 60 + 5;
const int maxw = 2e5 + 50;
int dp[maxn][maxw];
int n, m;

struct node{
    int v, w, q, f1, f2; 
}a[maxn];

int calc( int i ) {
    return a[i].v * a[i].w;
}

int main()
{	
    cin >> n >> m;
    for( int i = 1; i <= m; ++ i )
    {
        cin >> a[i].w >> a[i].v >> a[i].q;
        if( a[i].q )
        {
            if( !a[ a[i].q ].f1 ) a[ a[i].q ].f1 = i;
            else a[ a[i].q ].f2 = i;
        }
    }

    for( int i = 1; i <= m; ++ i )
    {
        for( int j = 1; j <= n; ++ j )
        {
            if( a[i].q )
            {
                dp[i][j] = dp[i-1][j];
            }
            else
            {
                int f1 = a[i].f1, f2 = a[i].f2;
                int t = dp[i-1][j];
                if( j >= a[i].w )
                    t = max( t, dp[i-1][j - a[i].w] + calc( i ) );
                if( f1 && j >= a[i].w + a[f1].w )
                    t = max( t, dp[i-1][j - a[i].w - a[f1].w ] + calc( i ) + calc( f1 ) );
                if( f2 && j >= a[i].w + a[f2].w )
                    t = max( t, dp[i-1][j - a[i].w - a[f2].w ] + calc( i ) + calc( f2 ) );
                if( f1 && f2 && j >= a[i].w + a[f1].w + a[f2].w )
                    t = max( t, dp[i-1][j - a[i].w - a[f1].w - a[f2].w ] + calc( i ) + calc( f1 ) + calc( f2 ) );
                dp[i][j] = t;
            }
        }
    }
    
    cout << dp[m][n];
    return 0;
}

4. 复盘

• 复杂度: $O( N \cdot M )$。

• 碎碎念: 依赖背包如果依赖关系复杂（比如树形），那就得用树形 DP。但本题附件少，所以可以手动展开，转化为分组背包解决。

• 关联笔记: 背包DP