通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(分治)的方式去解决:动态规划 (Dynamic Programming, DP)

多重背包模型

例题

来源:AcWing04 - 多重背包问题 I - https://www.acwing.com/problem/content/4/

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

第 $i$ 种物品最多有 $s_i$ 件,每件体积是 $v_i$,价值是 $w_i$。

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

输入格式

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

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

输出格式

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

数据范围

$0 \lt N, V \le 100$
$0 \lt v_i, w_i, s_i \le 100$

输入样例

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

输出样例

10

分析 & 代码

暴力解法

多重背包和完全背包的区别就是每一种物品取得数量有一个上限 $s_i$,那么可以直接用完全背包的暴力代码,在第三层循环限制下 $ k\leq s_i$ 就好了。

  • 时间复杂度:$O(N\cdot V^2)$ (最坏情况)
  • 空间复杂度:$O(V)$
#include <iostream>
#include <algorithm>

using namespace std;

const int SIZE = 1010;
int N, V;
int v[SIZE], w[SIZE], s[SIZE];
int dp[SIZE];

int main()
{
    cin >> N >> V;
    for (int i = 1; i <= N; i++)
        cin >> v[i] >> w[i] >> s[i];
    for (int i = 1; i <= N; i++)
        for (int j = V; j >= v[i]; j--)
            for (int k = 0; k * v[i] <= j && k <= s[i]; k++)
                dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);
    cout << dp[V] << endl;
    return 0;
}

二进制优化

暴力解法中第三层循环从 $1$ 遍历到了 $s_i$,当数据过大时,三层循环会超时,我们需要优化这个遍历过程。先看下面的例子:

一个数 $200$,我们可以将其拆为 $1,2,4,8,16,32,64,73$ 这 $8$ 个数,那么通过这 $8$ 个数的不同取法,我们可以拼凑出 $0\sim 200$ 的所有情况。因为 $1$ 可拼凑 $1$,$1,2$ 可拼凑 $1,2,3$,$1,2,4$ 可拼凑 $1,2,3,4,5,6,7$,以此类推即可得证。

那么对于任意一个数 $N$,我们都能找到一组数 $2^0,2^1,2^2,\cdots,2^k,N-2^{k+1}+1$,通过这一组数的不同取法拼凑出 $0\sim N$ 的所有数。

通过这种思想,我们改变第三层循环的方式,不去一个一个取物品,而是将物品每 $1$ 个、$2$ 个、$4$ 个……打包,然后分析打包好的包裹的不同取法,即变成了 01-背包问题。

  • 时间复杂度:$O(N\cdot\log{S}\cdot V)$
  • 空间复杂度:$O(V)$ (已包含空间优化)
#include <iostream>
#include <algorithm>

using namespace std;

// 需要注意各个数组的大小
const int SIZE_NlogS = 25000, SIZE_V = 2010;
int N, V, idx;
int v[SIZE_NlogS], w[SIZE_NlogS];
int dp[SIZE_V];

int main()
{
    cin >> N >> V;
    // 物品读入
    for (int i = 1; i <= N; i++)
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        // 物品打包
        while (k <= s)
        {
            v[++idx] = a * k;
            w[idx] = b * k;
            s -= k;
            k *= 2;
        }
        if (s)
        {
            v[++idx] = a * s;
            w[idx] = b * s;
        }
    }
    // 01-背包问题
    for (int i = 1; i <= idx; i++)
        for (int j = V; j >= v[i]; j--)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    cout << dp[V] << endl;
    return 0;
}

分组背包问题

例题

来源:AcWing09 - 分组背包问题 - https://www.acwing.com/problem/content/9/

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

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

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

输出最大价值。

输入格式

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

接下来有 $N$ 组数据:

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

输出格式

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

数据范围

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

输入样例

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

输出样例

8

分析

实际仍然能当作“01-背包问题”来看,只不过“01-背包问题”的每一个物品变成了一组物品,不过我们只用遍历这一组,求到这一组物品的最优情况即可。

  • 时间复杂度:$O(V\cdot\sum{S})$
  • 空间复杂度:$O(V)$ (已包含空间优化)
#include <bits/stdc++.h>

using namespace std;

const int SIZE = 110;
int N, V;
int v[SIZE][SIZE], w[SIZE][SIZE], S[SIZE];
int dp[SIZE];

int main()
{
    cin >> N >> V;
    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 = 0; i <= N; i++)
        for (int j = V; j >= 0; j--)
            for (int k = 0; k < S[i]; k++)
                if (v[i][k] <= j)
                    dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);
    cout << dp[V] << endl;
    return 0;
}

标签: 动态规划

添加新评论