算法提高课汇总

算法思路

理解题意

1. 限制
   • 价格<-->物品体积
   • 附件只有在购买其对应主件后才能购买(存在依赖关系)
2. 目标
   • Max价格$\times$重要度

我们可以把每个主件和其附件划为一组, 问题可以看作是有依赖关系的分组背包 问题.

$DP$分析

本题相对简单的地方是每个主件的附件最多只有2个, 所以我们可以在选择了主件$i$的基础上枚举附件选择
的所有状态, 并取最大值.

$for 物品 \rightarrow for 体积 \rightarrow for 决策$我的理解是$for 集合状态 \rightarrow for 决策$,即先确定状态再计算这个状态的值.

代码实现

这里即使主件价格为0也可能会购买其性价比高的附件. 所以用if (master[i].v)的判断可能会出错.

#include <vector>
#include <iostream>

#define v first
#define w second

using namespace std;

typedef pair<int, int> pii;

const int N = 60, M = 32010;

int n, m;
bool is_master[N];
pii master[N]; //主件
vector<pii> serv[N]; //附件
int dp[M];

int main()
{
    cin >> m >> n;
    for( int i = 1; i <= n; i ++ )
    {
        int v, w, q;
        cin >> v >> w >> q;
        if( q )     serv[q].push_back({v, v * w});
        else        master[i] = {v, v * w}, is_master[i] = true;
    }

    for( int i = 1; i <= n; i ++ )
    {
        if( is_master[i] )
        {//i是主件
            for( int j = m; j >= master[i].v; j -- )
            {//枚举的情况中一定会选择主件i, 否则dp[i][j] = dp[i - 1][j]对于一维空间是恒等式
                for( int k = 0; k < 1 << serv[i].size(); k ++ )
                {//二进制枚举所有附件的选择情况
                    int v = master[i].v, w = master[i].w;
                    for( int u = 0; u < serv[i].size(); u ++ )
                    {
                        if( k >> u & 1 )
                        {
                            v += serv[i][u].v;
                            w += serv[i][u].w;
                        }
                    }
                    if( j >= v )    dp[j] = max( dp[j], dp[j - v] + w );
                }
            }
        }
    }
    cout << dp[m] << endl;

    return 0;
}