动态规划(一)

发表于 分类于

动态规划

现在发现 DP 其实没学明白，

所以重新学习一遍动态规划。

背包问题

背包九讲的出处，y总亲讲 DP ，有兴趣的可以看一下

注意：背包不一定要装满


闫式 DP 分析法

以 01 背包为例

y总简洁优雅的板书

状态计算


01背包问题

每件物品最多可以选一次

分析

y总简洁优雅的板书

起点 ，
转移方程
终点

code

  • 朴素版本
1
2
3
4
5
6
7
for (int i = 1; i <= n; ++ i)
    for (int j = 0; j <= m; ++ j) {
        f[i][j] = f[i - 1][j];
        if (v[i] <= j) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
    }

printf("%d", f[n][m]);
  • 滚动数组优化

的计算只用到了 ，所以可以用滚动数组优化

1
2
3
4
5
6
7
8
9
10
11
int f[2][N];

for (int i = 1; i <= n; ++ i) {
    int now = i & 1, last = now ^ 1;
    for (int j = 0; j <= m; ++ j)  {
        f[now][j] = f[last][j];
        if (v[i] <= j) f[now][j] = max(f[now][j], f[last][j - v[i]] + w[i]);
    }
}

printf("%d", f[n & 1][m]);
  • 优化为一维

我们发现转移方程中 也就是说如果我们从后向前转移就不会有后效性

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

printf("%d", f[m]);


完全背包

每个物品可以选无限个

分析

image-20220128152110079

起点
转移方程
终点

code

  • 朴素版本
1
2
3
4
5
6
for (int i = 1; i <= n; ++ i)
    for (int j = 0; j <= m; ++ j)
        for (int k = 0; k * v[i] <= j; ++ k)
            f[i][j] = max(f[i][j], f[i- 1][j - k * v[i]] + k * w[i]);

cout << f[n][m] << endl;
  • 优化

image-20220128154545170

我们发现：

而：

所以有：

如果再加上以上所说的一维优化就有：

1
2
3
4
5
for (int i = 1; i <= n; ++ i)
    for (int j = v[i]; j <= m; ++ j)
        f[j] = max(f[j], f[j - v[i]] + w[i]);

cout << f[m] << endl;

PS: 以前只是将其理解为顺序遍历,一种物品会被”取”好多次，但是现在发现原来可以从数学角度证明。y总 tql ，一听就懂


多重背包

每个物品只能选有限个

分析

image-20220128161602762

起点
转移方程
终点

code

  • 朴素版本
1
2
3
4
5
6
for (int i = 1; i <= n; ++ i)
    for (int j = 0; j <= m; ++ j)
        for (int k = 0; k <= s[i] && k * v[i] <= j; ++ k)
            f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + w[i] * k);

cout << f[n][m] << endl;
  • 二进制优化

证明：将一个正整数 拆分为整数 ，可以表示出 中的任意整数

其中： ，这里要使得 最大

根据倍增的思想 可以表示 中的任意整数

我们让其加上 就有：原拆分可以表示 中的任意整数

即证明：

显然：

所以原命题成立。

证毕。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 2010;
int f[N];
struct good { int v, w; };
int main() {
    int n, m;
    vector<good> goods;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i) {
        int v, w, s;
        scanf("%d%d%d", &v, &w, &s);
        for (int k = 1; k <= s; s -= k, k <<= 1)
            goods.push_back({k * v, k * w});
        if (s) goods.push_back({s * v, s * w});
    }
    for (auto [v, w]: goods)
        for (int j = m; j >= v; -- j)
            f[j] = max(f[j], f[j - v] + w);
    cout << f[m] << endl;
}


分组背包

每组物品有若干个，同一组内的物品最多只能选一个。

分析

image-20220128170619779

起点
转移方程
终点

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i) {
        scanf("%d", s + i);
        for (int j = 1; j <= s[i]; ++ j) scanf("%d%d", &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]);
    printf("%d", f[m]);
}