前言

AcWing算法提高课内容，本文讲解 动态规划

本篇包括以下题目：

⭐️ AcWing 12. 背包问题求具体方案
⭐️ AcWing 9. 分组背包问题
⭐️ AcWing 1013. 机器分配
⭐️ AcWing 734. 能量石

写博客有哪里不完善的地方或者有哪里表达错误希望大家提出来，博主会立即改正！望大家海涵

本文需要先自修基础：背包问题

注：本文中的所有代码全部为优化后的代码，且不提供优化解释，解释请见：背包问题，其中有详细的解释。

背包问题求具体方案

题目要求

题目描述：

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

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

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

输出 字典序最小 的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 $1\dots N$。

输入格式：

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

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

输出格式：

输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。

物品编号范围是 $1\dots N$。

数据范围：

$0<N,V\le 1000$
$0<v_i,w_i\le 1000$

输入样例：

4 5
1 2
2 4
3 4
4 6

  

 

  
1
  
2
  
3
  
4
  
5
 

输出样例：

1 4

  

 

  
1
 

思路分析

注意，因为要求输出的顺序是按照字典序，故我们在进行 $dp$ 的过程中，枚举样本需要从大到小枚举，这样我们在按照字典序输出的时候就可以正向循环，查看状态 $i$ 是由哪个状态 $j$ 转移而来的 $(j>i)$

代码

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

using namespace std;

const int N = 1010;

int v[N], w[N];
int f[N][N];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
    for (int i = n; i >= 1; i -- )
        for (int j = 0; j <= m; j ++ )
        {
            f[i][j] = f[i + 1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
        }
    
    int j = m;
    for (int i = 1; i <= n; i ++ )
        if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i])
        {
            cout << i << ' ';
            j -= v[i];
        }
        
    return 0;
}

  

 

  
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
 

分组背包问题

题目要求

题目描述：

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

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 $v_{ij}$，价值是 $w_{ij}$，其中 $i$ 是组号，$j$ 是组内编号。

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

输出最大价值。

输入格式：

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

接下来有 $N$ 组数据：

• 每组数据第一行有一个整数 $S_i$，表示第 $i$ 个物品组的物品数量；
• 每组数据接下来有 $S_i$ 行，每行有两个整数 $v_{ij},w_{ij}$，用空格隔开，分别表示第 $i$ 个物品组的第 $j$ 个物品的体积和价值；

输出格式：

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

数据范围：

$0<N,V\le 100$
$0<S_i\le 100$
$0<v_{ij},w_{ij}\le 100$

输入样例：

3 5
2
1 2
2 4
1
3 4
1
4 5

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
 

输出样例：

8

  

 

  
1
 

思路分析

裸题，不解释，解释见博客：背包问题

代码

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

using namespace std;

const int N = 110;

int v[N][N], w[N][N], s[N];
int f[N];

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

  

 

  
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
 

机器分配

题目要求

题目描述：

总公司拥有 $M$ 台相同的高效设备，准备分给下属的 $N$ 个分公司。

各分公司若获得这些设备，可以为国家提供一定的盈利。盈利与分配的设备数量有关。

问：如何分配这 $M$ 台设备才能使国家得到的盈利最大？

求出最大盈利值。

分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数 $M$。

输入格式：

第一行有两个数，第一个数是分公司数 $N$，第二个数是设备台数 $M$；

接下来是一个 $N\ast M$ 的矩阵，矩阵中的第 $i$ 行第 $j$ 列的整数表示第 $i$ 个公司分配 $j$ 台机器时的盈利。

输出格式：

第一行输出最大盈利值；

接下 $N$ 行，每行有 $2$ 个数，即分公司编号和该分公司获得设备台数。

答案不唯一，输出任意合法方案即可。

数据范围：

$1\le N\le 10,$
$1\le M\le 15$

输入样例：

3 3
30 40 50
20 30 50
20 25 30

  

 

  
1
  
2
  
3
  
4
 

输出样例：

70
1 1
2 1
3 1

  

 

  
1
  
2
  
3
  
4
 

思路分析

可以看做分组背包问题：即每个公司分配的设备数是唯一的，并且要求具体的分配方案，即：背包问题求具体方案；这里其实有两种写法，代码一为按照本博客中的题目：背包问题求具体方案 进行倒枚举，但需注意，倒枚举的话输出的应为：$f[1][m]$，另一种方法就是记录分配过程，这种方法就不需要进行倒枚举。

代码一

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

using namespace std;

const int N = 15, M = 20;

int w[N][M];
int f[N][M];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            cin >> w[i][j];
            
    for (int i = n; i >= 1; i -- )
        for (int j = 0; j <= m; j ++ )
            for (int k = 0; k <= j; k ++ )
                f[i][j] = max(f[i][j], f[i + 1][j - k] + w[i][k]);
                
    cout << f[1][m] << endl;   // 注意是 f[1][m]
    
    int j = m;
    for (int i = 1; i <= n; i ++ )
        for (int k = 0; k <= j; k ++ )
            if (f[i][j] == f[i + 1][j - k] + w[i][k])
            {
                cout << i << ' ' << k << endl;
                j -= k;
                break;
            }
    
    return 0;
}

  

 

  
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
 

代码二

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

using namespace std;

const int N = 15, M = 20;

int w[N][M];
int f[N][M];
int ways[N];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            cin >> w[i][j];
            
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ )
            for (int k = 0; k <= j; k ++ )
                f[i][j] = max(f[i][j], f[i - 1][j - k] + w[i][k]);
                
    cout << f[n][m] << endl;
    
    int j = m;
    for (int i = n; i >= 1; i -- )
        for (int k = 0; k <= j; k ++ )
            if (f[i][j] == f[i - 1][j - k] + w[i][k])
            {
                ways[i] = k;
                j -= k;
                break;
            }
        
    for (int i = 1; i <= n; i ++ )
        cout << i << ' ' << ways[i] << endl;
    
    return 0;
}

  

 

  
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
 

能量石

题目要求

题目描述：

岩石怪物杜达生活在魔法森林中，他在午餐时收集了 $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 105,$
$0\le L_i\le 105$

输入样例：

3
4
20 10 1
5 30 5
100 30 1
5 80 60
3
10 4 1000
10 3 1000
10 8 1000
2
12 300 50
5 200 0

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
 

输出样例：

Case #1: 105
Case #2: 8
Case #3: 500

  

 

  
1
  
2
  
3
 

样例解释：
在样例 ＃1 中，有 $N=4$ 个宝石。杜达可以选择的一个吃石头顺序是：

• 吃第四块石头。这需要 $5$ 秒，并给他 $80$ 单位的能量。
• 吃第二块石头。这需要 $5$ 秒，并给他 $5$ 单位的能量（第二块石头开始时具有 $30$ 单位能量，$5$ 秒后失去了 $25$ 单位的能量）。
• 吃第三块石头。这需要 $100$ 秒，并给他 $20$ 单位的能量（第三块石头开始时具有 $30$ 单位能量，$10$ 秒后失去了 $10$ 单位的能量）。
• 吃第一块石头。这需要 $20$ 秒，并给他 $0$ 单位的能量（第一块石头以 $10$ 单位能量开始，$110$ 秒后已经失去了所有的能量）。

他一共获得了 $105$ 单位的能量，这是能获得的最大值，所以答案是 $105$。

在样本案例 ＃2 中，有 $N=3$ 个宝石。

无论杜达选择吃哪块石头，剩下的两个石头的能量都会耗光。

所以他应该吃第三块石头，给他提供 $8$ 单位的能量。

在样本案例 ＃3 中，有 $N=2$ 个宝石。杜达可以：

• 吃第一块石头。这需要 $12$ 秒，并给他 $300$ 单位的能量。
• 吃第二块石头。这需要 $5$ 秒，并给他 $200$ 单位的能量（第二块石头随着时间的推移不会失去任何能量！）。

所以答案是 $500$。

思路分析

本题难度较大，用的是：贪心+动态规划，其中 $f[i]$ 表示恰好用了 $i$ 的时间的情况下的最大能量值，故我们的最终能量最大值 $res$ 需要枚举一遍从 $f[1]$ 到 $f[m]$，因为恰好用了 $m$ 时间并不一定是最大值，由于我们状态方程设置的是恰好，而不是不大于，故我们需要对状态方程进行初始化：

memset(f, -0x3f, sizeof f);
f[0] = 0;

  

 

  
1
  
2
 

这样就能保证我们的每一个状态都是由初始状态转移而来，接下来进入贪心分析：

我们来分析两个石头：石头 $i$ 和石头 $j$，先吃 $i$ 和先吃 $j$ 的能量关系，如过先吃 $i$ 得到的能量大于等于先吃 $j$ 得到的能量，那么有不等式：$E_i+E_j-S_i\ast L_j>=E_i+E_j-S_j\ast L_i$，化简有：$S_j\ast L_i>=S_i\ast L_j$，即我们可以先对数组按照 $S_j\ast L_i>=S_i\ast L_j$ 进行排序，排序后的次序枚举即为我们选择吃能量石的顺序，在这个顺序下可以保证获得的能量石最大的。

我们的状态转移方程为：f[j] = max(f[j], f[j - s] + max(0, e - (j - s) * l));，即能量石的能量石可能衰减为负数的，但题中规定衰减到 $0$ 后就不再进行能量衰减，故我们需要和 $0$ 取一个 $max$。

代码

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

using namespace std;

const int N = 110, M = 10010;

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

int f[M];

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

  

 

  
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
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
 

文章来源: chen-ac.blog.csdn.net，作者：辰chen，版权归原作者所有，如需转载，请联系作者。

原文链接：chen-ac.blog.csdn.net/article/details/123717062