动态规划

背包问题

0-1 背包问题

问题描述

有 $N$ 件物品和容量为 $V$ 的背包, 每件物品只能使用一次. 第 $i$ 件物品的体积为 $v_{i}$ 价值为 $w_{i}$,
从中选择一些物品装入背包, 求解使物品总体积不超过背包容量的最大价值.

数据范围

$0 < N, V < 1000, 0 < v_{i}, w_{i} < 1000$.

样例

输入

4 5
1 2
2 4
3 4
4 5

输出

8

算法1

状态表示:

• 集合
  $f[i][j]$ 表示从前 $i$ 个物品当中选取体积不超过 $j$ 的选法的集合.

• 属性
  集合中不同选法的价值的最大值

状态计算:

• 集合划分
  $f[i][j]$ 可划分为拿第 $i$ 件物品体积不超过 $j$ 的集合 $\cup$ 不拿第 $i$ 件物品体积不超过 $j$ 的集合, 因此就有
  $f[i][j] = max(f[i - 1][j], f[i - 1][j - v_{i}] + w_{i})$, $i = 1, 2, …, N. j = 1, 2, …, V.$

时间复杂度

循环物品数量和体积, 所以是 $O(NV)$.

c++ 代码

#include<iostream>

using namespace std;

const int N = 1010;

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

int main(){
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; ++ 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]);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

算法2

使用滚动数组优化, 用一维数组表示, 从上面的代码修改得到.

c++ 代码

#include<iostream>

using namespace std;

const int N = 1010;

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

int main(){
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) cin >> v[i] >> w[i];
    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]);
        }
    }
    cout << f[m] << endl;
    return 0;
}

完全背包问题

问题描述

有 $N$ 件物品和容量为 $V$ 的背包, 每件物品可无限次使用. 第 $i$ 件物品的体积为 $v_{i}$ 价值为 $w_{i}$,
从中选择一些物品装入背包, 求解使物品总体积不超过背包容量的最大价值.

数据范围

$0 < N, V < 1000, 0 < v_{i}, w_{i} < 1000$.

样例

输入

4 5
1 2
2 4
3 4
4 5

输出

10

算法1

状态表示:

• 集合
  $f[i][j]$ 表示从前 $i$ 个物品当中选取体积不超过 $j$ 的选法的集合.

• 属性
  集合中不同选法的价值的最大值

状态计算:

• 集合划分
  $f[i][j]$ 可划分为拿第 $i$ 件物品 $0$ 次体积不超过 $j$ 的集合 $\cup$ 拿第 $i$ 件物品 $1$ 次体积不超过 $j$ 的集合 $\cup$ … $\cup$ 拿第 $i$ 件物品 $k$ 次体积不超过 $j$ 的集合 $\cup$ …, 因此就有
  $f[i][j] = max(f[i - 1][j], f[i - 1][j - v_{i}] + w_{i}, f[i - 1][j - 2v_{i}] + 2w_{i}, …,f[i - 1][j - kv_{i}] + kw_{i}, …)$, $i = 1, 2, …, N.$

时间复杂度

循环物品数量和体积还有个数, 所以是 $O(NV^{2})$.

c++ 代码

#include<iostream>

using namespace std;

const int N = 1010;

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

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i) scanf("%d%d", &v[i], &w[i]);
    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;
    return 0;
}

算法2

在上述状态计算中
$$ f[i][j] = max(f[i - 1][j], f[i - 1][j - v_{i}] + w_{i}, f[i - 1][j - 2v_{i}] + 2w_{i}, …,f[i - 1][j - kv_{i}] + kw_{i}, …) $$
注意到
$$ f[i][j-v_{i}] = max(f[i - 1][j - v_{i}], f[i - 1][j - 2v_{i}] + w_{i}, f[i - 1][j - 3v_{i}] + 2w_{i}, …,f[i - 1][j - (k + 1)v_{i}] + kw_{i}, …) $$
所以就有
$$ f[i][j] = max(f[i][j], f[i][j - v_{i}] + w_{i}) $$

时间复杂度

循环物品数量和体积, 所以是 $O(NV)$.

c++ 代码

#include<iostream>

using namespace std;

const int N = 1010;

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

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i) scanf("%d%d", &v[i], &w[i]);
    for (int i = 1; i <= n; ++ 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][j - v[i]] + w[i]);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

算法3

加上滚动数组优化

时间复杂度

循环物品数量和体积, 所以是 $O(NV)$.

c++ 代码

#include<iostream>

using namespace std;

const int N = 1010;

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

int main(){
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) cin >> v[i] >> w[i];
    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;
    return 0;
}

多重背包问题

问题描述

有 $N$ 件物品和容量为 $V$ 的背包. 第 $i$ 件物品的体积为 $v_{i}$ 价值为 $w_{i}$ 数量为 $s_{i}$, 从中选择一些物品装入背包, 求解使物品总体积不超过背包容量的最大价值.

数据范围

$0 < N, V < 100, 0 < v_{i}, w_{i}, s[i] < 100$.

样例

输入

4 5
1 2
2 4
3 4
4 5

输出

10

算法1

状态表示:

• 集合
  $f[i][j]$ 表示从前 $i$ 个物品当中选取体积不超过 $j$ 的选法的集合.

• 属性
  集合中不同选法的价值的最大值

状态计算:

• 集合划分
  $f[i][j]$ 可划分为拿第 $i$ 件物品 $0$ 次体积不超过 $j$ 的集合 $\cup$ 拿第 $i$ 件物品 $1$ 次体积不超过 $j$ 的集合 $\cup$ … $\cup$ 拿第 $i$ 件物品 $k$ 次体积不超过 $j$ 的集合 $\cup$ …, 因此就有
  $f[i][j] = max(f[i - 1][j], f[i - 1][j - v_{i}] + w_{i}, f[i - 1][j - 2v_{i}] + 2w_{i}, …,f[i - 1][j - kv_{i}] + kw_{i})$, $i = 1, 2, …, N.$

时间复杂度

循环物品数量和体积还有个数, 所以是 $O(NV^{2})$.

c++ 代码

#include<iostream>

using namespace std;

const int N = 110;

int f[N][N], v[N], w[N], s[N];#include<iostream>

using namespace std;

const int N = 110;

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

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

int main(){
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) cin >> v[i] >> w[i] >> s[i];
    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]] + k * w[i]);
            }
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

算法2

在上述状态计算中
$$ f[i][j] = max(f[i - 1][j], f[i - 1][j - v_{i}] + w_{i}, f[i - 1][j - 2v_{i}] + 2w_{i}, …,f[i - 1][j - kv_{i}] + kw_{i}) $$
注意到
$$ f[i][j-v_{i}] = max(f[i - 1][j - v_{i}], f[i - 1][j - 2v_{i}] + w_{i}, f[i - 1][j - 3v_{i}] + 2w_{i},\\ …,f[i - 1][j - kv_{i}] + (k - 1)w_{i} ,f[i - 1][j - (k + 1)v_{i}] + kw_{i}) $$
多了最后一项, 所以无法使用完全背包的优化.

下面使用了滚动数组优化.

c++ 代码

#include<iostream>

using namespace std;

const int N = 110;

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

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

算法3

当数据规模较大的时候, 上面介绍的方法会超时.

• 二进制优化
  考虑将一定数量的物品进行组合成一件物品, 使得这种物品的任意数量均可以有这些物品通过组合得到.
  然后剩余的过程就是求解一个 01 背包问题.
  设一件物品的数量为 s,
  s 可以分解为 $1, 2, 4, 8, …, 2^{i-1}, s-(2^{i} - 1)$, 这些不同数量的物品组成新的物品加入原来的物品当中, 然后求解 01 背包问题

#include<iostream>

using namespace std;

const int N = 12010, M = 2010;

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

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

分组背包问题

问题描述

有 $N$ 组物品和容量为 $V$ 的背包. 第 $i$ 组物品的体积为 $v_{ij}$ 价值为 $w_{ij}$ 数量为 $s_{i}$, 从每组选择至多一个物品装入背包, 求解使物品总体积不超过背包容量的最大价值.

数据范围

$0 < N, V < 100, 0 < v_{ij}, w_{ij}, s[ij] < 100$.

样例

输入

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

输出

8

算法1

状态表示:

• 集合
  $f[i][j]$ 表示从前 $i$ 组物品当中选取体积不超过 $j$ 的选法的集合.

• 属性
  集合中不同选法的价值的最大值

状态计算:

• 集合划分
  $f[i][j]$ 可划分为不拿第 $i$ 组物品体积不超过$j$ 的集合 $\cup$ 拿第 $i$ 组物品中的第一个物品体积不超过$j$ 的集合 $\cup$ … $\cup$ 拿第 $i$ 组物品中的第s[i]个物品体积不超过$j$ 的集合$\cup$, 因此就有
  $f[i][j] = max(f[i - 1][j], f[i - 1][j - v_{i1} + w_{i1}, f[i - 1][j - v_{i2}] + w_{i2}, …,f[i - 1][j - v_{is[i]}] + w_{is[i]})$, $i = 1, 2, …, N.$

时间复杂度

循环物品数量和体积还有个数, 所以是 $O(NV^{2})$.

c++ 代码

#include<iostream>

using namespace std;

const int N = 105;

int s[N], w[N][N], v[N][N], f[N][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 = 0; j <= m; ++ j) {
            f[i][j] = f[i - 1][j];
            for (int k = 1; k <= s[i]; ++ k) {
                if (j >= v[i][k])
                    f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
            }
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

算法二

#include<iostream>

using namespace std;

const int N = 110;

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

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