动态规划模板

包含了ACM一些常用的动态规划模型

思维导图：

image-20220717193651501

数字三角形模型

每次只能向下走或者向右走。从起点走到终点。

题目给定一个 n×nn \times n 的矩阵，矩阵中的每个格子上有一个价值为 ww 的物品。给定起点 (1,1)(1,1) 和终点 (n,n)(n, n) ，规定只能向下或者向右走。从起点出发两次，但同一个格子在两次路径中都经过的话，他的物品价值只会被累加一次。问两次路线，途径格子的物品的总价值最大是多少。

注意到每次走一步，横纵坐标的和都会加1.且知道横坐标，纵坐标，和两个坐标的和的任意两个就能知道另外一个。这就启示我们可以状态压缩。

另外两次行动可以看成一起同步行动。通过这样的想法就定义出 dp[i][j][k]dp[i][j][k] 表示 aa 路线当前横坐标为 ii ，bb 路线当前横坐标为 jj ，横纵坐标和为 kk 时的最大总价值。

状态只能由 dp[i−1][j][k−1],dp[i][j−1][k−1],dp[i][j][k−1],dp[i−1][j−1][k−1]dp[i - 1][j][k-1],dp[i][j - 1][k- 1],dp[i][j][k - 1],dp[i-1][j-1][k-1] 这四者中转移过来。如果两点不重合，再加上 a[i][k−i],a[j][k−1]a[i][k-i],a[j][k-1] ，否则只要加上 a[i][j−i]a[i][j-i] 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
ll n;
ll a[15][15];
ll dp[15][15][30]; //横纵坐标为k=i+j时的最大值

bool check(int x, int y) {
    //是否非法
    if (x < 1 || x > n || y < 1 || y > n) return true;
    return false;
}

void solve() {
    n = read();
    while (1) {
        int u = read(), v = read(), w = read();
        if (!u && !v && !w) break;
        a[u][v] = w;
    }
    dp[1][1][2] = 0;
    //目标：dp[n][n][2n]
    for (int k = 3; k <= 2 * n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                int ax = i, ay = k - i, bx = j, by = k - j;
                if (check(ax, ay) || check(bx, by)) continue;
                ll w1 = dp[ax - 1][bx - 1][k - 1], w2 = dp[ax][bx - 1][k - 1];
                ll w3 = dp[ax - 1][bx][k - 1],  w4 = dp[ax][bx][k - 1];
                ll w = max(max(w1, w2), max(w3, w4));
                if (ax == bx) 
                    //两个点是同一个点
                    dp[i][j][k] = max(dp[i][j][k], w + a[ax][ay]);
                else 
                    //两个点不是同一个点
                    dp[i][j][k] = max(dp[i][j][k], w + a[ax][ay] + a[bx][by]);
            }
        }
    }
    printf("%lld\n", dp[n][n][2 * n]);
}

最长上升子序列模型

最长上升子序列：dp[i] = min{dp[j] + 1}, a[j] < a[i], j < i

最长公共子序列：dp[i] = min{dp[j] + 1}, a[j] = a[i], j < i

最长上升/下降子序列模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
ll n;
ll a[MAXN];
ll dpl[MAXN], dpr[MAXN];
void solve() {
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    dpl[1] = 1;
    for (int i = 2; i <= n; i++) {
        ll mx = 0;
        for (int j = 1; j < i; j++) 
            if (a[j] < a[i])
                mx = max(mx, dpl[j]);
        dpl[i] = mx + 1;
    }
    dpr[n] = 0;
    for (int i = n - 1; i; i--) {
        ll mx = -1;
        for (int j = n; j > i; j--) 
            if (a[j] < a[i])
                mx = max(mx, dpr[j]);
        dpr[i] = mx + 1;
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, dpl[i] + dpr[i]);
    printf("%lld\n", ans);
}

经典的拦截导弹模型。

这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。

求两个量，最多能拦截的导弹数和拦截所有导弹最少要配备的系统数

第一个问题求数组的最长非上升子序列，第二个问题求该数组最少能被几个最长下降子序列覆盖。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
ll n;
ll a[MAXN];
ll dp1[MAXN];
ll dp2[MAXN];
void solve() {
    n = 0;
    ll tmp;
    while (scanf("%lld", &tmp) != EOF) {
        ++n;
        a[n] = tmp;
    }
    ll ans1 = 0;
    dp1[1] = 1;
    for (int i = 2; i <= n; i++) {
        ll mx = 0;
        for (int j = 1; j < i; j++) 
            if (a[j] >= a[i])
                mx = max(mx, dp1[j]);
        dp1[i] = mx + 1;
    }
    for (int i = 1; i <= n; i++) ans1 = max(ans1, dp1[i]);
    printf("%lld\n", ans1);
    dp2[1] = 1;
    for (int i = 2; i <= n; i++) {
        ll mx = 0;
        for (int j = 1; j < i; j++) 
            if (a[j] < a[i])
                mx = max(mx, dp2[j]);
        dp2[i] = mx + 1;
    }
    ll ans2 = 0;
    for (int i = 1; i <= n; i++) ans2 = max(ans2, dp2[i]);
    printf("%lld\n", ans2);
}

最长上升公共子序列

状态表示 dp[i][j]dp[i][j] （集合）： 考虑 aa 中前 ii 个数，bb 中前 jj 个数字，且当前以 b[j]b[j] 结尾的子序列方案

状态表示 dp[i][j]dp[i][j] （属性）：maxmax

状态转移：

  • 从 aa 中前 i−1i - 1 个数，bb 中前 jj 个数转移 dp[i][j]=max(dp[i][j],dp[i−1][j])dp[i][j] = max(dp[i][j],dp[i-1][j])
  • 从 aa 中前 ii 个数，bb 中前 kk 个数且以 b[k]b[k] 为结尾的子序列方案转移过来 dp[i][j]=max(dp[i][j],dp[i−1][k]+1),k∈[1,j−1],ai=bjdp[i][j] = max(dp[i][j],dp[i-1][k] +1),k\in[1,j-1],a_i=b_j

每次遍历通过维护一个前缀最大值的方案可以省去一维的时间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ll n;
ll a[MAXN];
ll b[MAXN];
ll dp[MAXN][MAXN]; //a前i个，b前j个，且以bj为结尾的最长上升公共子序列
void solve() {
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i <= n; i++) b[i] = read();
    ll mx = 0;
    for (int i = 1; i <= n; i++) {
        ll mx = 0;
        for (int j = 1; j <= n; j++) {
            dp[i][j] = dp[i - 1][j];
            if (a[i] == b[j]) dp[i][j] = max(mx + 1, dp[i][j]);
            if (b[j] < a[i]) mx = max(mx, dp[i - 1][j]);
                // for (int k = 1; k < j; k++) 
                //     if (b[j] > b[k])
                //         dp[i][j] = max(dp[i - 1][k] + 1, dp[i][j]);         
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, dp[n][i]);
    printf("%lld\n", ans);
}

背包模型

01背包求最值

1
2
3
4
5
6
7
8
9
10
11
for (int i = 1; i <= n; i++)
    for (int j = V; j >= v[i]; j--) 
        dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= V; j++) {
        dp[i][j] = dp[i - 1][j];
        if (j >= v[i])
            dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
    }
}

二维费用背包（就比01背包多开了一维）

1
2
3
4
for (int i = 1; i <= n; i++) 
    for (int j = V; j >= v[i]; j--) 
        for (int k = M; k >= m[i]; k--) 
            dp[j][k] = max(dp[j][k], dp[j - v[i]][k - m[i]] + w[i]);

01背包求方案数（记得初始化）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ll n, V;
ll v[MAXN];
ll dp[MAXM];
void solve() {
    n = read(), V = read();
    dp[0] = 1;
    for (int i = 1; i <= n; i++) v[i] = read();
    for (int i = 1; i <= n; i++) {
        for (int j = V; j >= v[i]; j--) {
            dp[j] += dp[j - v[i]];
        }
    }
    printf("%lld\n", dp[V]);
}

完全背包求最值（可以无限次选择）

遍历 jj 的时候从倒着遍历改成正的遍历就行了

完全背包求方案数。同求最值，改成正着遍历；注意初始化。

多重背包（单调队列优化）

物品数量有限，求最大价值。

价值 w[i]w[i] ，体积 v[i]v[i] ，个数 s[i]s[i]

令 r=jr = j modmod viv_i ，也可以理解为完全背包下把当前物品选到不能再选后，剩下的余数。

可以推出公式 dp(i,r)=dp(i−1,r)dp(i,r)=dp(i-1,r) 。

下述公式的第一个维度省略掉了，因为之和前一维有关

  • dp(i,r)=dprdp(i,r) = dp_r
  • dp(i,r+v)=max(dpr+v,dpr+w)dp(i,r+v) = max(dp_{r+v},dp_r+w)
  • dp(i,r+2v)=max(dpr+2v,dpr+v+w,dpr+2w)dp(i,r+2v) = max(dp_{r+2v},dp_{r+v}+w,dp_r+2w)
  • …
  • dp(i,r+sv)=max(dpr+sv,dpr+(s−1)v+w,...,dpr+sw)dp(i,r+sv)=max(dp_{r+sv},dp_{r+(s-1)v} +w,...,dp_r+sw) 滑动窗口已满
  • dp(i,r+(s+1)v)=max(dpr+(s+1)v,dpr+sv+w,...,dpr+v+sw)dp(i,r+(s+1)v)=max(dp_{r+(s+1)v},dp_{r+sv}+w,...,dp_{r+v}+sw) 滑动窗口已满
  • …
  • dp(i,j−2v)=max(dpj−2v,dpj−3v+w,...,dpj−(s+2)v+sw)dp(i,j-2v)=max(dp_{j-2v},dp_{j-3v}+w,...,dp_{j-(s+2)v}+sw)
  • dp(i,j−v)=max(dpj−v,dpj−2v+w,...,dpj−(s+1)v+sw)dp(i,j-v)=max(dp_{j-v},dp{j-2v}+w,...,dp_{j-(s+1)v}+sw)
  • dp(i,j)=max(dpj,dpj−v+w,...,dpj−sw+sw)dp(i,j)=max(dp_j,dp_{j-v}+w,...,dp_{j-sw}+sw)

由此可见，滑动窗口大小为 s[i]+1s[i]+1

通过该滑动窗口，就能在线性的时间里求出 ii 阶段中，所有满足 j=rj=r modmod v[i]v[i] 的 dp(i,j)dp(i,j)

滑动窗口求最大值的实现，可以利用维护一个最大值单调递减的单调队列。

枚举所有的余数 rr 即可 (0,v[i]−1)(0,v[i]-1)

不要忘记比较使得偏移量 ww 。

具体就是当前下标和最大值的下标之间差了 xx 个 v[i]v[i] ，那么就要加上 xx 个 w[i]w[i]

时间复杂度 O(n×v)O(n \times v) 空间复杂度 O(n×v)O(n \times v) 滑动窗口长度 s[i]+1s[i]+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
ll v[MAXN], w[MAXN], s[MAXN], V, n;
ll q[MAXM]; //存放体积
ll dp[2][MAXM]; //滚动数组
void solve() {
    n = read();
    V = read();
    for (int i = 1; i <= n; i++) {
        v[i] = read();
        w[i] = read();
        s[i] = read();
    }
    for (int i = 1; i <= n; i++) {
        for (int r = 0; r < v[i]; r++) { //枚举模数
            int hh = 1, tt = 0;
            for (int j = r; j <= V; j += v[i]) { //枚举模数恒为r的体积
                
                int now = i & 1;
                int pre = (i - 1) & 1;
                while (hh <= tt && dp[pre][q[tt]] + (j - q[tt]) / v[i] * w[i] <= dp[pre][j])
                    tt--; //保证队列单调递减
                q[++tt] = j;
                while (hh <= tt && j - q[hh] > v[i] * s[i]) 
                    hh++;  //加上当前要加入的元素，窗口元素大于s[i]+1，超过限制
                dp[now][j] = dp[pre][q[hh]] + (j - q[hh]) / v[i] * w[i];
            }
        }
    }
    printf("%lld\n", dp[n & 1][V]);
}

多重背包（二进制优化）

这个就好理解多了。所有数都可以被看成 1+2+4+...+n−2k+11+2+4+...+n-2^k+1 。这样的话 s[i]=1+2+4+...+2k−1,s[i]−(2k−1)s[i] = 1 + 2+4+...+2^{k-1},s[i]-(2^k-1) 。那么就可以当成若干个01背包中的物品了。体积是 x×vx \times v ，价值是 x×wx \times w

时间复杂度 O(n2logs)O(n^2logs) ，其中 ss 表示所有物品的数量之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
ll n, V;
ll v[MAXN], w[MAXN], s[MAXN];
ll dp[MAXM];
void solve() {
    n = read(), V = read();
    for (int i = 1; i <= n; i++) {
        v[i] = read();
        w[i] = read();
        s[i] = read();
    }
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= s[i]; k *= 2) { //二进制枚举，分解成若干01背包
            ll tmpv = k * v[i];
            ll tmpw = k * w[i];
            for (int j = V; j >= tmpv; j--)
                dp[j] = max(dp[j - tmpv] + tmpw, dp[j]);
            s[i] -= k;
        }
        if (s[i]) { //最后的一部分，单独处理一下
            ll tmpv = s[i] * v[i];
            ll tmpw = s[i] * w[i];
            for (int j = V; j >= tmpv; j--)
                dp[j] = max(dp[j - tmpv] + tmpw, dp[j]);
        }
    }
    printf("%lld\n", dp[V]);
}

混合背包

物品分三类：只能取一次，能取无限次，能取 s[i]s[i] 次。使总价值最大。

针对三类物品做不同的状态转移即可，具体参考前文。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
ll n, V;
ll v[MAXN], w[MAXN], s[MAXN];
ll dp[MAXN];
void solve() {
    n = read(), V = read();
    for (int i = 1; i <= n; i++) {
        v[i] = read();
        w[i] = read();
        s[i] = read();
    }
    for (int i = 1; i <= n; i++) {
        if (!s[i]) //完全背包
            for (int j = v[i]; j <= V; j++)
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        else if (s[i] == -1)  //01背包
            for (int j = V; j >= v[i]; j--) 
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        else {
            //多重背包
            for (int k = 1; k <= s[i]; k *= 2) {
                for (int j = V; j >= k * v[i]; j--)
                    dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);
                s[i] -= k;
            }
            if (s[i])
                for (int j = V; j >= s[i] * v[i]; j--)
                    dp[j] = max(dp[j], dp[j - s[i] * v[i]] + s[i] * w[i]);
        }        
    }
    printf("%lld\n", dp[V]);
}

一些变形

可以放置超过背包容量的物品，体积至少为xxx：

即当前背包预留的容量可以由负数转移过来（看成0）

1
2
3
4
5
6
memset(dp, 0x3f, sizeof dp);
dp[0][0] = 0;
for (int i = 1; i <= n; i++) 
    for (int j = V; j >= 0; j--) 
        for (int k = M; k >= 0; k--) 
            dp[j][k] = min(dp[j][k], dp[max(0ll, j - v[i])][max(0ll, k - m[i])] + w[i]);

体积恰好为xxx

改变状态转移方程的前提条件。要么之前 i−1i-1 时当前这个体积已经有方案了，要么只能有体积为 00 的状态转移过来。

1
2
3
4
5
if (j >= v[i] && (j == v[i] || dp[i - 1][j - v[i]]) != 0)
   dp[i][j] = (dp[i][j] + dp[i - 1][j - v[i]]) % mod;

if (j == v[i] / 2 || dp[i - 1][j - v[i] / 2] != 0)
   dp[i][j] = (dp[i][j] + dp[i - 1][j - v[i] / 2]) % mod;

输出方案

有 nn 件物品和一个容量为 VV 的背包。第 ii 件物品的体积是 viv_i ，价值是 wiw_i ，每件物品只能用一次。求解一种方案，使得选择的物品总体积小于 VV ，且总价值最大，输出字典序最小的方案。

做法就是先做一遍正常的背包 DPDP ，然后从目标状态倒退回初始状态的整个转移路径

伪代码：

1
2
3
4
5
6
7
8
9
10
int v = V;  // 记录当前的存储空间

// 因为最后一件物品存储的是最终状态，所以从最后一件物品进行循环
for (从最后一件循环至第一件) {
  if (g[i][v]) {
    选了第 i 项物品;
    v -= 第 i 项物品的价值;
  } else
    未选第 i 项物品;
}

题目还要求了字典序最小。在倒退转移方程时，如果碰到物品既可以选也可以不选，优先的选项是选择该物品。因此，背包 DPDP 是倒过来 (从n到1)，然后再从 11 倒推会 nn 找出路径。这样，如果出现分叉情况是，就优先选当前物品即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
ll n, V;
ll dp[MAXN][MAXN];
ll v[MAXN], w[MAXN];
int path[MAXN], cnt = 0; //保存路径

void dfs(int i, ll j) {
    if (i == n + 1) return;
    if (j >= v[i] && dp[i][j] == dp[i + 1][j - v[i]] + w[i]) {
        path[++cnt] = i;
        dfs(i + 1, j - v[i]); //选择当前物品
    }
    else
        dfs(i + 1, j); //不选择当前物品
}

void solve() {
    n = read(), V = read();
    for (int i = 1; i <= n; i++) v[i] = read(), w[i] = read();
    for (int i = n; i >= 1; i--) {
        for (int j = 0; j <= V; j++) {
            dp[i][j] = dp[i + 1][j]; //状态复制
            if (j >= v[i])
                dp[i][j] = max(dp[i][j], dp[i + 1][j - v[i]] + w[i]);
        }
    }       
    // for (int i = 1, j = V; i <= n; i++) {
    //     if (j >= v[i] && dp[i + 1][j - v[i]] + w[i] == dp[i][j]) {
    //         //选了当前的物品，把他扔掉
    //         path[++cnt] = i;
    //         j -= v[i];
    //     }
    // }       
    dfs(1, V);
    for (int i = 1; i <= cnt; i++) printf("%d ", path[i]);
}

分组背包+输出方案

题目：总公司拥有 MM 台设备，准备分给下属的 nn 个分公司。第 ii 家公司分到 jj 台机器后，所获得的收益为 wijw_{ij} 。求一种分配方案，使得总收益最大，输出该方案。

分析：每家公司都可以看成一个物品组，又因为每家公司最终能够被分配的机器数量是固定的，因此对于分给第 ii 个公司的不同机器数量可以分别看做是一个物品组内的物品。

  • 物品含义：分为第 ii 个公司 kk 台机器
  • 物品体积：kk
  • 该物品 kk 的价值：wikw_{ik}

image-20220717193713940

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
ll n, m;
ll a[25][25];
ll dp[25][25];
int path[25], cnt;

void dfs(int now, int v) {
    if (!now) return; //所有物品都选完了
    for (int i = 0; i <= m; i++) {
        if (v >= i && dp[now][v] == dp[now - 1][v - i] + a[now][i]) {
            path[now] = i;
            dfs(now - 1, v - i);
            return; //同一组内只能选一个，选完直接return
        }
    }
}

void solve() {
    n = read(), m = read();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            a[i][j] = read();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = dp[i - 1][j]; //状态转移，先假设不选当前组内物品
            for (int k = 1; k <= j; k++) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k] + a[i][k]);
            }
        }
    }
    printf("%lld\n", dp[n][m]);
    // for (int i = n, j = m; i >= 1; i--) {
    //     for (int k = 0; k <= m; k++) {
    //         if (j >= k && dp[i][j] == dp[i - 1][j - k] + a[i][k]) {
    //             j -= k;
    //             path[i] = k;
    //             break; //同一组内只能选一个，选完后就break掉
    //         }
    //     }
    // }
    dfs(n, m);
    for (int i = 1; i <= n; i++) printf("%d %d\n", i, path[i]);
}

这是分组背包最裸的模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ll n, V;
ll v[MAXN][MAXN], w[MAXN][MAXN], dp[MAXN][MAXN], cnt[MAXN];
void solve() {
    n = read(), V = read();
    for (int i = 1; i <= n; i++) {
        cnt[i] = read();
        for (int j = 1; j <= cnt[i]; j++)
            v[i][j] = read(), w[i][j] = read();
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= V; j++) {
            dp[i][j] = dp[i - 1][j];
            for (int k = 1; k <= cnt[i]; k++) {
                if (j >= v[i][k])
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i][k]] + w[i][k]);
            }
        }
    }
    printf("%lld\n", dp[n][V]);
}

压缩成一维后：

1
2
3
4
5
6
for (int i = 1; i <= n; i++) //枚举物品组
    for (int j = V; j >= 0; j--) //枚举给当前物品组分配的体积
        for (int k = 1; k <= cnt[i]; k++) //枚举物品
            if (j >= v[i][k]) 
                dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);         
printf("%lld\n", dp[V]);

01背包求最优方案数

思路就是先求一次 dpdp ，再搞一次逆推方案。

空间不优化写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
ll n, V;
ll v[MAXN], w[MAXN];
ll mx;
ll dp[MAXN][MAXN]; //最优价值
ll cnt[MAXN][MAXN]; //方案数量
void solve() {
    n = read(), V = read();
    for (int i = 1; i <= n; i++) v[i] = read(), w[i] = read();   
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= V; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i])
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }
    } 
    cnt[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= V; j++) {
            if (dp[i][j] == dp[i - 1][j])
                cnt[i][j] = (cnt[i][j] + cnt[i - 1][j]) % mod;
            if (j >= v[i] && dp[i - 1][j - v[i]] + w[i] == dp[i][j])
                cnt[i][j] = (cnt[i][j] + cnt[i - 1][j - v[i]]) % mod;
        }
    }
    ll ans = 0;
    for (int i = 0; i <= V; i++) 
        if (dp[n][i] == dp[n][V])
            ans = (ans + cnt[n][i]) % mod;
    printf("%lld\n", ans);
}

空间优化成一维后：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
ll n, V;
ll v[MAXN], w[MAXN];
ll mx;
ll dp[MAXN];
ll cnt[MAXN];
void solve() {
    n = read(), V = read();
    for (int i = 1; i <= n; i++) v[i] = read(), w[i] = read();  
    cnt[0] = 1; 
    for (int i = 1; i <= n; i++) {
        for (int j = V; j >= v[i]; j--) {
            ll tmp = max(dp[j], dp[j - v[i]] + w[i]);
            ll now = 0;
            if (tmp == dp[j - v[i]] + w[i])
                now = (now + cnt[j - v[i]]) % mod;
            if (tmp == dp[j])
                now = (now + cnt[j]) % mod;
            dp[j] = tmp, cnt[j] = now;
        }
    } 
    ll ans = 0;
    for (int i = 0; i <= V; i++) 
        if (dp[i] == dp[V])
            ans = (ans + cnt[i]) % mod;
    printf("%lld\n", ans);
}

有依赖的背包问题（树上背包）

有 nn 件物品和一个体积为 VV 的背包。第 ii 件物品的体积为 v[i]v[i] ，价值为 w[i]w[i] ，每件物品有一个父节点物品 p[i]p[i] ，如果想选第 ii 件物品，就必须选他的父节点 p[i]p[i] 。求能选出的最大价值。

首先，这种依赖关系类似于树中的父节点和子节点，于是用树形DP来做。

考虑到根据方案划分的话，有 2x2^x 种状态，显然存不下。因此考虑根据体积来划分，枚举每棵子树的共用体积。（这个过程有点像分组背包）

状态表示集合：考虑第 ii 个物品为根节点的子树，且选上 ii ，选法的总体积不超过 jj 的方案。

状态表示属性：方案的总价值最大 MaxMax

状态计算：

image-20220717193727229

image-20220717193735209

时间复杂度 O(n×V×V)O(n\times V\times V)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
ll n, V;
ll v[MAXN], w[MAXN];
ll dp[MAXN][MAXN];
int root;

void dfs(int now, int pre) {
    //先枚举所有体积小于等于V-v[now]的所有子节点们能获得的最大价值
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to; //枚举物品组
        if (to == pre) continue;
        dfs(to, now); //用子节点更新父节点，树形DP，从下往上算
        for (int j = V - v[now]; j >= 0; j--) //所有子节点的体积和 实测j=V开始也行，因为这个状态最终会被废弃（覆盖）掉
            for (int k = 0; k <= j; k++) //枚举物品，对应被分配到的体积
                dp[now][j] = max(dp[now][j], dp[now][j - k] + dp[to][k]);
    }
    //最后选上当前的根节点now物品
    for (int j = V; j >= v[now]; j--) dp[now][j] = dp[now][j - v[now]] + w[now];
    for (int j = 0; j < v[now]; j++) dp[now][j] = 0; //清空没选上now的所有状态
}

void solve() {
    n = read(), V = read();
    for (int i = 1; i <= n; i++) {
        int fa;
        v[i] = read(), w[i] = read(), fa = read();
        if (fa == -1) root = i;
        else add_edge(fa, i), add_edge(i, fa);
    }
    dfs(root, -1);
    printf("%lld\n", dp[root][V]);
}

亿点点细节：枚举子节点的共用体积 jj 时要倒着枚举，因为确保当前一层只被更新一次。根节点物品最后才计算，因为这样能防止被覆盖掉。体积小于 v[now]v[now] 的要被清零，因为这是有依赖关系的，子节点生效的前提条件是选了当前父节点。

有依赖的背包问题（体积和价值在边上）

给定一颗含有 nn 个节点的树，树根编号为 11 ，且树上的每一条边有一个边权 w[i]w[i] 。要求保留树中的 mm 条边，使得树根所在的连通块的所有边边权之和最大。

定义状态dp[i][j]dp[i][j] ，以 ii 为根节点的子树，包含 ii 的连通块的边数不超过 jj 的方案。

当点作为体积时，第一重循环的 jj 可以取 V−v[now]V - v[now] 也可以取 VV ，因为根据状态的定义，必须选当前节点的体积，另外多枚举的部分在之后会被覆盖掉。当边作为体积时， jj 只能从 VV 开始而不是 V−1V -1 ，因为假设当前是根节点的话就少枚举了。

kk 则对应决策方案，为某个子树被分到的体积。枚举 kk 的时候最大到 j−1j - 1，是因为如果计算该子树对父节点的贡献，必须保留他到父节点的边。

代码可以和上一道好好对比

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
ll n, m;
struct EDGE {
    int to, next, val;
}edge[MAXM];
int head[MAXN], tot;
void add(int from, int to, int val) {
    edge[++tot].to = to, edge[tot].val = val, edge[tot].next = head[from], head[from] = tot;
}
ll dp[MAXN][MAXN];

void dfs(int now, int pre) {
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        int val = edge[i].val;
        if (to == pre) continue;
        dfs(to, now);
        for (int j = m; j >= 0; j--) { //体积
            for (int k = 0; k < j; k++) { //决策，预留一条连向父节点的边
                dp[now][j] = max(dp[now][j - k - 1] + dp[to][k] + val, dp[now][j]);
            }
        }        
    }
}

void solve() {
    n = read(), m = read();
    for (int i = 1; i < n; i++) {
        int u = read(), v = read(), w = read();
        add(u, v, w);
        add(v, u, w);
    }
    dfs(1, -1);
    printf("%lld\n", dp[1][m]);
}

有依赖的背包问题，根节点不止一个（森林）

可以利用图论中超级源点中的思想，建一个虚拟源点连接所有的根节点，这样森林就变成了一棵树。然后定义这个虚拟源点的体积为 11 ，或者任何正数，在总体积中加上虚拟源点的体积正常做树上背包即可。例题中所有节点体积都为 11 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int n, V;
int dp[MAXN][MAXN];
int w[MAXN];

void dfs(int now, int pre) {
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        if (to == pre) continue;
        dfs(to, now);
        for (int j = V; j >= 0; j--) //枚举体积 
            for (int k = 0; k <= j; k++)
                dp[now][j] = max(dp[now][j - k] + dp[to][k], dp[now][j]);
    }
    for (int j = V; j >= 1; j--)
        dp[now][j] = dp[now][j - 1] + w[now];
    dp[now][0] = 0;
}

void solve() {
    n = read(), V = read();
    V++;
    for (int i = 1; i <= n; i++) {
        int fa;
        fa = read(), w[i] = read();
        add(fa, i), add(i, fa);
    }
    dfs(0, -1);
    printf("%d\n", dp[0][V]);
}

有依赖的背包问题（分组背包）

一共有 nn 个物品和 VV 体积的背包。

物品之间可能存在依赖关系，每个物品体积为 v[i]v[i], 价值为 w[i]w[i] ，依赖的父亲物品为 p[i]p[i]，每个物品只能被购买一次。

求一种购买方案，使得总花费不超过 VV ，且总价值最大。

注意，每个父亲的儿子不超过两个，且儿子不会再有儿子。

如果按照体积划分，时间复杂度 O(n×V×V)O(n \times V \times V) 就会超时了。

注意到每个主件的附属品不超过两个，且附属品不会再有附属品。因此可以采用分组背包对本题的状态进行划分。具体做法就是用类似于状态压缩的方法，二进制枚举所有情况，每种组合对应一个物品组内的一个物品。时间复杂度 O(n×22×V)O(n \times 2^2 \times V)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
ll V, n;
ll v[MAXN], w[MAXN];
bool isfa[MAXN]; //判断是否为主件
vector<int> g[MAXN];
ll dp[MAXM];

void init() {
    for (int i = 1; i <= n; i++) g[i].clear(), isfa[i] = false;
}

void work(int now, ll j) {
    int len = g[now].size(); //当前分组内的物品
    //类似于状态压缩的方法，因为数量不多，直接二进制遍历所有的状态，相当于枚举所有的方案
    for (int st = 0; st < (1 << len); st++) {
        int sum_v = v[now];
        ll sum_w = w[now];
        for (int i = 0; i < len; i++) {
            if (st >> i & 1) 
                sum_v += v[g[now][i]], sum_w += w[g[now][i]]; 
        }
        if (sum_v <= j)
            dp[j] = max(dp[j], dp[j - sum_v] + sum_w);
    }
}

void solve() {
    V = read(), n = read();
    init();
    for (int i = 1; i <= n; i++) {
        int fa;
        v[i] = read(), w[i] = read(), fa = read();
        w[i] = w[i] * v[i];
        if (fa) g[fa].pb(i);
        else isfa[i] = true;
    }
    for (int i = 1; i <= n; i++)
        if (isfa[i]) //枚举物品组
            for (int j = V; j >= v[i]; j--) //枚举分配给物品组的体积
                work(i, j);
    printf("%lld\n", dp[V]);
}