数据结构与算法学习笔记（Acwing提高课）----动态规划·背包模型(四）

数据结构与算法学习笔记----动态规划·背包模型(四）

@@ author: 明月清了个风
@@ first publish time: 2025.5.18

ps⭐️这一篇中包含:

1️⃣完全背包问题的两道例题：货币系统(Acwing 1021与Acwing 532)；

2️⃣混合背包的模版题：Acwing 7;

3️⃣有依赖的背包问题模版题：Acwing 10，之前已经有过一道了(Acwing 487. 金明的预算方案)，可以看这篇链接，类似的思想还有基础课中的树形DP，可以去看一下

4️⃣背包问题求方案数：Acwing 11.这里的方案数和Acwing 1021.货币系统并不一样，要求的是能够实现最大价值的方案数。

Acwing 1021. 货币系统

给你一个$n$种面值的货币系统，求组成面值为$m$的货币有多少种方案。

输入格式

第一行，包含两个整数$n$和$m$。

接下来$n$行，每行包含一个整数，表示一种货币的面值。

输出格式

共一行，包含一个整数，表示方案数。

数据范围

$n\le 15$, $m\le 3000$

思路

每种货币可以拿无限个，因此可以归类为完全背包问题求方案数。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1010;

int n, m;
LL f[N];

int main()
{
    cin >> n >> m;
    
    f[0] = 1;
    for(int i = 1; i <= n; i ++)
    {
        int a;
        cin >> a;
        for(int j = 0; j <= m; j ++)
        {
            if(j >= a) f[j] += f[j - a];
        }
    }
    
    cout << f[m] << endl;
    
    return 0;
}

Acwing 532. 货币系统

在网友的国度中共有$n$种不同面值的货币，第$i$种货币的面额为$a[i]$，你可以假设每一种货币都有无穷多张。

为了方便，我们把货币种数为$n$，面额数组为$a[\mathrm{1..}n]$的货币系统记作$(n,a)$。

在一个完善的货币系统中，每一个非负整数的金额$x$都应该可以被表示出，即对每一个非负整数$x$，都存在$n$个非负整数$t[i]$满足$a[i]\times t[i]$的和为$x$。

然而，在网友的国度中，货币系统可能是不完善的，即可能存在金额$x$不能被货币系统表示出。

例如在货币系统$n=3$,$a=[2,5,9]$中，金额$1，3$就无法被表示出来。

两个货币系统$(n,a)$与$(m,b)$是等价的，当且仅当对于任意非负整数$x$,它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。

现在网友们打算简化一下货币系统。

他们希望找到一个货币系统$(m,b)$与原来的货币系统$(n,a)$等价，且$m$尽可能的小。

他们希望你来协助完成这个艰巨的任务：找到最小的$m$。

输入格式

输入文件的第一行包含一个整数$T$，表示数据的组数。

接下来按照如下格式分别给出$T$组数据。

每组数据的第一行包含一个正整数$n$。

接下来一行包含$n$个由空格隔开的正整数$a[i]$。

输出格式

输出文件共有 $T $行，对于每组数据，输出一行一个正整数，表示所有与$ (n,a)$等价的货币系统$ (m,b)$中，最小的$m$。

数据范围

$1\le n\le 100$,

$1\le a[i]\le 25000$,

$1\le T\le 20$，

思路

根据题意，要找到一个有最少成员的整数组使其能够表示的货币完全与原货币系统$(n,a)$相同。

那么很显然，我们要找的这个货币系统的成员一定少于或等于原货币系统，少掉的成员就是能够被数组内成员自我表示的，如货币系统$(3,6,10,19)$中，$6$和$19$就是可以去掉的成员，因为能被$3$和$10$表示。

并且可以发现，我们要找的这个货币系统$(m,b)$中的所有$b_i$一定属于原货币系统$a$，因为如果不属于的话，那么$b_i$一定是能够被$a_i$表示的，那么既然不属于原货币系统，所以$b_i$肯定是由多个$a_i$表示的，但是由于我们找到的$(m,b)$符合题意，那么所有的$a_i$肯定是能够被新的货币系统中的其他$b_j$表示的， 因此$b_i$就是多余元素。因此得证，所有的$b_i$一定就是$a_i$中的成员，而不是多个$a_i$的线性组合，这个性质大幅降低了我们要判断的空间，因为最多只有$100$个$a_i$。

进一步地，根据上面这一点，所有的$b_i$一定是不能被其他$b_j$表示的，否则就能去掉了。

题目转化为了在原货币系统中选个$m$个$a_i$作为新的货币系统，那么对于所有的$a_i$来说，肯定是越小越好，因为大的可能被小的表示，因此对所有$a_i$从小到大排序后开始选择，每到一个$a_i$就要看他是否能被$a_1\sim a_{i-1}$表示出来，如果可以，那么$a_i$肯定不选，如果不能，那就要选择。

如何判断就是一个完全背包问题了，也就是用$a_1\sim a_{i-1}$的物品，每个物品有无限个，是否能够装满容积恰好为$a_i$的背包。上一题是计算有几种方案，而这题就是判断方案是否为$0$。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 110, M = 25010;

int T;
int a[N];
int f[M];

int main()
{
    cin >> T;
    
    while(T --)
    {
        int n;
        cin >> n;
        
        for(int i = 1; i <= n; i ++) cin >> a[i];
        sort(a + 1, a + n + 1);
        
        int m = a[n];
        memset(f, 0, sizeof f);
        f[0] = 1;
        
        int res = 0;
        for(int i = 1; i <= n; i ++)
        {
            if(!f[a[i]]) res ++;
            for(int j = a[i]; j <= m; j ++) 
                f[j] += f[j - a[i]];
        }
        cout << res << endl;
    }
    
    return 0;
}

Acwing 7. 混合背包问题

有$N$种物品和一个容量是V的背包。

物品一共有三类：

• 第一类物品只能用$1$次；
• 第二类物品可以用无限次；
• 第三类物品最多只能用$s_i$次。

每种物品体积是$v_i$，价值是$w_i$。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式

第一行两个整数，$N,V$，用空格隔开，分别表示物品种数和背包容积。

接下来$N$行， 每行三个整数$v_i,w_i,s_i$，用空格隔开，分别表示第$i$种物品的体积、价值和数量。

$s_i=-1$表示第$i$种物品只能用$1$次；

$s_i=0$表示第$i$种物品可以用无限次；

$s_i>0$表示第$i$种物品可以使用$s_i$次。

输出格式

输出一个整数，表示最大价值。

数据范围

$0<N,V<1000$

$0<v_i,w_i\le 1000$,

$-1\le s_i\le 1000$

思路

就是三种背包问题的结合版，那么对于状态表示而言，这里就是$f[i][j]$，表示的是只从前$i$种物品中选，且总体积不超过$j$的选法集合，要求的属性是最大值。

对于状态计算，$01$背包问题的是$f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])$；完全背包的是$f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i])$；多重背包问题的是$f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i],\cdots )$

由于对于第$i$个物品来说，无论前面的物品是什么类型都不会影响其选择方法，因此只要考虑第$i$件物品的类型即可。

需要注意的是，题目的数据给的比较大，如果所有物品都是多重背包的话，可能会导致超时，因此要使用多重背包的优化版本。由于$01$背包问题可以看成特殊的多重背包问题，因此可以一起处理。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int f[N];

int main()
{
    cin >> n >> m;
    
    for(int i = 0; i < n; i ++)
    {
        int v, w, s;
        cin >> v >> w >> s;
        
        if(s == 0)
        {
            for(int j = v; j <= m; j ++)
                f[j] = max(f[j], f[j - v] + w);
        }
        else
        {
            if(s == -1) s = 1;
            int k = 1;
            while(s >= k)
            {
                int sv = k * v;
                int sw = k * w;
                for(int j = m; j >= sv; j --)
                    f[j] = max(f[j], f[j - sv] + sw);
                s -= k;
                k *= 2;
            }
            if(s)
            {
                for(int j = m; j >= s * v; j --)
                    f[j] = max(f[j], f[j - s * v] + s * w);
            }
        }
    }
    
    cout << f[m] << endl;
    
    return 0;
}

Acwing 10. 有依赖的背包问题

有$N$种物品和一个容量是V的背包。

物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。

如下图所示：

如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。

每件物品的编号是$i$，体积是$v_i$，价值是 $wi$，依赖的父节点编号是$ pi$。物品的下标范围是 $1\dots N$。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值

输入格式

第一行两个整数，$N,V$，用空格隔开，分别表示物品种数和背包容积。

接下来$N$行， 每行数据表示一个物品。

第$i$行有三个整数$v_i,w_i,p_i$，用空格隔开，分别表示物品的体积、价值和依赖的物品编号。

如果$p_i=-1$，表示根节点，数据保证所有物品构成一棵树。

输出格式

输出一个整数，表示最大价值。

数据范围

$1<N,V<100$

$1\le v_i,w_i\le 100$

父节点编号范围：

• 内部节点$1\le p_i\le N$;
• 根节点$p_i=-1$;

思路

可以看到这道题中的所有物品构成了一棵树，与讲过的Acwing 487. 金明的预算方案不同的是，所有的点都被连接在同一颗树里。因此不能再像之前那样每个物品单独考虑了。这里的状态表示变为$f[u][j]$，表示从以$u$为根的子树中选择，且总体积不超过$j$的方案，要求的属性是最大值。

对于状态计算，很明显需要根据以$u$为根的子树的叶节点选择情况进行划分。需要注意的是，这里的子节点可能会有很多，在金明的预算方案这题中，我们根据附件的选择情况进行划分，因为最多只会有两个附件，因此只有$2^2=4$种情况，而如果这里达到最大值可能会有$2^{100}$种情况，因此不能按照每个子节点的选择情况划分。这里的划分方式按照体积进行划分。也就是对于每一个子树而言，可以使用$x$个体积在子树中选择节点，且对于每个子树而言，只会有一种情况，此时在子树中的选择就变成分组背包问题。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int f[N][N];
int v[N], w[N];
int h[N],e[N],ne[N],idx;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u)
{
    // 搜索当前节点的所有子节点，即子树
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int son = e[i];
        dfs(e[i]);
        
        for(int j = m - v[u]; j >= 0; j --)
        {
            for(int k = 0; k <= j; k ++)
                f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]); 
                // 1. 不选子树son，那就是f[u][j]；
                // 2. 选择子树son，那么为子树son预留k体积就是f[u][j - k]，再加上以son为根的子树体积为k就是f[son][k]；
        }
    }
    // 根据题意，选择了u节点才能选择u的子节点，因此体积一定要大于v[u]才能选择，否则直接赋值为0
    // 所有有足够体积的(i >= v[u])就把u节点的价值加上去。
    for(int i = m; i >= v[u]; i --) f[u][i] = f[u][i - v[u]] + w[u];
    for(int i = 0; i < v[u]; i ++) f[u][i] = 0;
}

int main()
{
    cin >> n >> m;
    int root;
    
    memset(h, -1, sizeof h);
    for(int i = 1; i <= n; i ++)
    {
        int p;
        cin >> v[i] >> w[i] >> p;
        if(p == -1) root = i;
        else add(p, i);
    }
    
    dfs(root);
    
    cout << f[root][m] << endl;
    
    return 0;
}

Acwing 11. 背包问题求方案数

有$N$种物品和一个容量是V的背包。每件物品只能使用一次。

第$i$件物品的体积是$v_i$，价值是$w_i$。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大

输出最优选法的方案数。注意答案可能很大，请输出答案模$ 10^9+7$的结果。

输入格式

第一行两个整数，$N,V$，用空格隔开，分别表示物品种数和背包容积。

接下来$N$行， 每行两个整数$v_i,w_i$，用空格隔开，分别表示第$i$件物品的体积、价值

输出格式

输出一个整数，表示方案数模$10^9+7$的结果。

数据范围

$0<N,V\le 1000$

$0\le v_i,w_i\le 1000$

思路

这道题的思路类似于求最短路径的条数，对于每一条走到终点的最短路路径，等于所有走到最短路径上一点的路径的总和，在这里也是一样，当我们更新$f[i][j]$的时候，同时记录能够更新$f[i][j]$的方案的总和即可，使用一个数组$g[i][j]$记录。

首先要求最大值，就是$f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])$，那么取到最大值的方案数就是：如果前一项更大，那就是加上$g[i-1][j]$；如果是后一项大，那就是加上$g[i-1][j-v[i]]$；如果前后一样大，那就两项都加上。

需要注意的是，这里是一个$01$背包问题，因此可以对存储空间进行优化，对于数组$g$来说同样可以进行这样的操作。

第二点需要注意的是，在这里状态表示的是体积恰好为$j$，因为我们求出最优选法对应的价值，且不能对其进行压缩，在之前的题目中，大多使用的状态表示是体积不超过$j$，这样其实会导致一个问题，最后的最优选法的体积可能并不正好是$j$，当然这里也可以这样做，不过就要进行处理了，处理方法是容斥原理。简单来说，最优选法可能对应的体积是$k$，那么$f[n][k]\sim f[n][m]$之间所有的值都会被更新为这个最大值，当我们计算路径的时候，就会重复计算，可通过容斥原理进行处理。

代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int n, m;
int f[N];
int g[N];

int main()
{
    cin >> n >> m;
    
    memset(f, -0x3f, sizeof f);
    f[0] = 0;
    g[0] = 1;
    
    for(int i = 1; i <= n; i ++)
    {
        int v, w;
        cin >> v >> w;
        for(int j = m; j >= v; j --)
        {
            int maxv = max(f[j], f[j - v] + w);
            int cnt = 0;
            if(f[j] == maxv) cnt += g[j];
            if(f[j - v] + w == maxv) cnt += g[j - v];
            g[j] = cnt % mod;
            f[j] = maxv;
            
        }
    }
    
    int res = 0;
    for(int i = 0; i <= m; i ++) res = max(res, f[i]);
    
    int cnt = 0;
    for(int i = 0; i <= m; i ++)
        if(res == f[i])
            cnt = (cnt + g[i]) % mod;
    
    cout << cnt << endl;
    
    return 0;
}

Acwing 734. 能量石

岩石怪物杜达生活在魔法森林中，他在午餐时收集了$N$块能量石准备开吃。

由于他的嘴很小，所以一次只能吃一块能量石。

能量石很硬，吃完需要花不少时间。

吃完第$i$块能量石需要花费的时间为$s_i$秒。

杜达靠吃能量石来获取能量。

不同的能量石包含的能量可能不同。

此外，能量石会随着时间流逝逐渐失去能量。

第$i$块能量石最初包含$E_i$单位的能量，并且每秒将失去$L_i$单位的能量。

当杜达开始吃一块能量石时，他就会立即获得该能量石所含的全部能量（无论实际吃完该石头需要多少时间）。

能量石中包含的能量最多降低至$0$。

请问杜达通过吃能量石可以获得的最大能量是多少？

输入格式

第一行包含整数$T$，表示共有$T$组测试数据。

每组数据第一行包含整数$N$，表示能量石的数量。

接下来$N$行，每行包含三个整数 $S_i,E_i,L_i$。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为Case #x: y，其中$x$是组别编号(从1开始),$y$是可以获得的最大能量值。

数据范围

$1\le T\le 10$,

$1\le N\le 100$,

$1\le s_i\le 100$,

$1\le E_i\le 10^5$,

$0\le L_i\le 10^5$，

思路

这一题很明显和吃能量石的顺序有关，因为在吃某一个能量石的时候会损失另一个能量石的能量，很容易想到要在顺序上发掘性质。因此考虑两个相邻的能量石$i，i+1$,吃这两个能量石能够获得的能量是$E_i+E_j-S_i\times L_{i+1}$，当然需要保证两者的能量都是大于$0$的。反之，先吃$i+1$的话，获得能量为$E_{i+1}+E_i-S_{i+1}\times L_i$。要比出这两种方案的好坏就是对比两个能量之间的大小，首先前两项是一样的，因此消去。如果是前者更好，那就意味着有$S_i\times L_{i+1}<S_{i+1}\times L_i$,因此对于任意吃的顺序，符合下面的式子的顺序是最优的：
$$\frac{S_i}{L_i}<\frac{S_{i+1}}{L_{i+1}}$$
这和在基础课中讲过的贪心问题中的推公式的思路是完全一致的，可以去复习一下，链接在这，证明过程也可以参考。

也就是说只要将所有能量石按照这个方案进行排序，最优解一定符合这个式子。

状态表示使用$f[i][j]$，表示所有只从前$i$块能量石中选，且总体积(这里是总用时)恰好为$j$的方案集合，属性是最大值。

状态计算也是一样的，如果不选择第$i$块能量石，那么就是$f[i-1][j]$，如果选择了，那就是$f[i-1][j-s]+e-(j-s)\ast L$，因为吃了第$i$块能量石到了时间$j$，所以开始吃的时间就是$j-s$，那就是在吃第$i$块能量石时已经过去了$j-s$的时间，因此吃它的时候已经失去了$(j-s)\ast L$的能量。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 10010;

int n;
struct Stone
{
    int s, e, l;
    bool operator< (const Stone W)const
    {
        return s * W.l < W.s * l;
    }
}stone[N];
int f[N];

int main()
{
    int T;
    cin >> T;
    for(int C = 1; C <= T; C ++)
    {
        int m = 0;
        cin >> n;
    
        for(int i = 0; i < n; i ++)
        {
            int s, e, l;
            cin >> s >> e >> l;
            stone[i] = {s, e, l};
            m += s;
        }
        
        sort(stone, stone + n);
        
        memset(f, -0x3f, sizeof f);
        f[0] = 0;
        
        for(int i = 0; i < n; i ++)
        {
            int s = stone[i].s, e = stone[i].e, l = stone[i].l;
            for(int j = m; j >= s; j --)
                f[j] = max(f[j], f[j - s] + e - (j - s) * l);
        }
        
        int res = 0;
        for(int i = 0; i <= m; i ++) res = max(res, f[i]);
        printf("Case #%d: %d\n", C, res);
    }
    
    return 0;
}