背景

弱化版

入题之前，先看看弱化版【开心的金明】

对于这道题，比平常所作的01背包多了一个重要度。
但仔细想想，背包问题主要是考虑价值与空间的比值(即性价比)。
只需将原物品价值乘以重要度即可。
$$dp[j]=max(dp[j],dp[j−价值]+贡献)$$

弱化Code

Code ED：

//算法:01背包
//时间复杂度:O(n^2)
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int N = 5e5+9;

struct Node{
    int t,v;
}g[N];
int n,m;
int dp[N];

signed main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        cin >> g[i].t >> g[i].v;
        g[i].v = g[i].t*g[i].v;
    }
    for(int i = 1; i <= m; ++i){
        for(int j = n; j >= 0; --j){
            if(j >= g[i].t)
                dp[j] = max(dp[j], dp[j-g[i].t]+g[i].v);
        }
    }
    cout << dp[n] << "\n";
    return 0;
}

强化版

现在入题【金明的预算方案】

题目大意

又多了一对关系:主件与附件。

主件可以单独购买，附件需要购买相应的主件后才开放购买。
0对应主件，其它数字对应是附件所对应的主件编号(注意:别被题目样例中只有0和1误导，附件对应数字不为0但对应所对应的主件编号。因为我被这绕了十分钟)。

问题主要是考虑对主件与附件进行区分和计算。

所以这道题本质上仍是01背包，不过多了些依赖关系，即为依赖背包。

变量存储

考虑主件与附件的对应关系，需要对他们进行编号。

使用一结构体方便些。

定义id为其编号，v为其价值，s为其总贡献，f为对应编号值(也可视为判断主附件)。

当然，我们仍需记录各项元素原数值。

定义n,m,v,p,q;为总钱数、空间、原价值、重要度和编号值。
再定义f[N]记录编号值，动转数组dp[N]。

变量命名

struct Node{
    int id,v,s,f;//编号、价值、总贡献、主附件判断
}g[N];
int n,m,v,p,q;
int f[N],dp[N];

判断主附件

因为需要判断主附件，所以它们的各项数值需要分开来记。
之前定义的q就可以判断(为0为主件，其它为附件)
这里:

if(q == 0)  g[i].id = i, g[i].v = v, g[i].s = v*p, g[i].f = 0;
        else  g[i].id = q, g[i].v = v, g[i].s = v*p, g[i].f = ++f[q];

编号排序

编号嘛，自然要排好序才好做。
直接利用结构体id编号即可。

bool sort1(Node a, Node b){//编号排序sort1函数
    if(a.id == b.id)  return a.f < b.f;
    return a.id < b.id;
}

样例

存储已经完毕，剩下的便是转移方程咯。
先手玩几把样例(必应之举)。

1000 5
800 2 0  买这个,还剩200块,贡献为800*2 = 1600
400 5 1  依赖1号物品
300 5 1  依赖1号物品
400 3 0  买这个,还剩600块,贡献为400*3 = 1200
500 2 0  买这个,还剩500块,贡献为500*2 = 1000

小贴士

(别把贡献当价格买，不然啥也买不起)
玩完#1样例后，发现买4、5号主件最值(1000+1200 = 2200)。

推理一下:那是不是存在部分数据，只选主件？
答案是肯定的。

购买情况

(不试你也行啊，DP肯定多情况啊，OI赛制是让你玩的?)

简单的动转方程：$$dp[j]=max(dp[j],dp[j−组合价格]+组合价值)$$
所以综合题目分析来看，存在以下四种情况:

$$
\begin{cases}
只买主件:max(dp[j], dp[j-g[i].v]+g[i].s)\
买主件和第一种附件:max(dp[j], dp[j-g[i].v-g[i+1].v]+g[i].s+g[i+1].s)\
买主件和第二种附件:max(dp[j], dp[j-g[i].v-g[i+2].v]+g[i].s+g[i+2].s)\
三件都买:max(dp[j], dp[j-g[i].v-g[i+1].v-g[i+2].v]+g[i].s+g[i+1].s+g[i+2].s)
\end{cases}
$$

强化Code

if条件得加附件编号对应主件编号，具体看代码吧。

Code ED:

//算法：依赖背包
//时间复杂度:O(n^2)
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int N = 4e5+10;

struct Node{
    int id,v,s,f;//编号、价值、总贡献、主附件判断
}g[N];
int n,m,v,p,q;
int f[N],dp[N];

bool sort1(Node a, Node b){//编号排序sort1函数
    if(a.id == b.id)  return a.f < b.f;
    return a.id < b.id;
}

signed main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        cin >> v >> p >> q;
        if(q == 0)  g[i].id = i, g[i].v = v, g[i].s = v*p, g[i].f = 0;
        else  g[i].id = q, g[i].v = v, g[i].s = v*p, g[i].f = ++f[q];
    }
    sort(g+1, g+m+1, sort1);//进行编号排序
    for(int i = 1; i <= m; ++i){
        if(g[i].f)  continue;
        for(int j = n; j >= g[i].v; --j){
            dp[j] = max(dp[j], dp[j-g[i].v]+g[i].s);//记录原始最大值(即只买主件)
            if(g[i+1].id == g[i].id  &&  j >= (g[i].v+g[i+1].v))//买第一个附件
                dp[j] = max(dp[j], dp[j-g[i].v-g[i+1].v]+g[i].s+g[i+1].s);
            if(g[i+2].id == g[i].id  &&  j >= (g[i].v+g[i+2].v))//买第二个附件
                dp[j] = max(dp[j], dp[j-g[i].v-g[i+2].v]+g[i].s+g[i+2].s);
            if(g[i+2].id == g[i].id  &&  j >= (g[i].v+g[i+1].v+g[i+2].v))//俩附件都买
                dp[j] = max(dp[j], dp[j-g[i].v-g[i+1].v-g[i+2].v]+g[i].s+g[i+1].s+g[i+2].s);//《g[i+1-g[i+2].v].v]》
        }
    }
    cout << dp[n] << "\n";
    return 0;
}

补充练习

【P1273 有线电视网】