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

01 背包模型

例题

来源：AcWing02 - 01背包问题 - https://www.acwing.com/problem/content/description/2/

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

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

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

输入格式

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

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

输出格式

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

数据范围

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

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例

8

分析

状态表示

集合：满足“在前 $i$ 个物品选择，总体积 $<j$ ”的条件的所有选法的集合。
属性：集合中选法价值的最大值。

综上，状态表示为：

$dp(i,j):=$ 从第 $1\sim i$ 个物品中选取，总体积 $<j$ 时，能取到的物品的最大总价值。

状态计算

集合划分：

$dp(i,j)$ 可划分为：

划分	结果
从 $1\sim i$ 个物品选取，总体积 $<j$ ，且不选第 $i$ 个物品的选法。	$dp(i-1,j)$
从 $1\sim i$ 个物品选取，总体积 $<j$ ，且选第 $i$ 个物品的选法。	$dp(i-1,j-v_i)+w_i$

因此，结果就是两个划分中的最大值，即 $dp(i,j)=\max\left\{dp(i-1,j),dp(i-1,j-v_i)+w_i\right\}$

解析：

如果在第 $1\sim i$ 个物品中选取，不取第 $i$ 个物品。那么这种情况和在第 $1\sim i-1$ 个物品中选取是相同的。

如果在第 $1\sim i$ 个物品中选取，取第 $i$ 个物品。这种情况直接考虑不方便，但可以通过间接方法。即考虑：在第 $1\sim i-1$ 个物品中选取，背包容量为 $j$ $-$ 第 $i$ 个物品的体积时，能取到的物品的最大总价值 $+$ 第 $i$ 个物品的价值。

代码

朴素版本

时间复杂度：$O(N\cdot V)$
空间复杂度：$O(N\cdot V)$

#include <iostream>
#include <algorithm>

using namespace std;

const int SIZE = 1010;
int N, V;             // N-物品数量 V-背包容积
int v[SIZE], w[SIZE]; // v-体积 w-价值
int dp[SIZE][SIZE];   // 二维动态规划

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

空间优化

上方代码可等价变形为此代码，将二维动态规划优化为了一维动态规划。原因是每一层 dp 时，只用到了上一层 dp 的数据，之前的数据是无用的。因此可以用滚动数组，计算出的新结果可以直接覆盖掉上一层的结果，这样只用一维数组就能解决该问题。

但直接改为滚动数组还有一个问题，第二层循环计算到 $j$ 的时候，比 $j$ 小的数据已经全部被新数据覆盖了，因为 $j-v[i]<j$，所以 $dp[i - 1][j - v[i]]$ 这个值已经被覆盖为了 $dp[i][j - v[i]]$。

要解决这个问题也很简单，我们可以反向循环，从大到小覆盖，这样就能保证我们需要用的值不被覆盖。

时间复杂度：$O(N\cdot V)$
空间复杂度：$O(V)$

#include <iostream>
#include <algorithm>

using namespace std;

const int SIZE = 1010;
int N, V;             // N-物品数量 V-背包容积
int v[SIZE], w[SIZE]; // v-体积 w-价值
int dp[SIZE];         // 一维动态规划

int main()
{
    cin >> N >> V;
    for (int i = 1; i <= N; i++)
        cin >> v[i] >> w[i];
    for (int i = 1; i <= N; 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;
}

完全背包模型

例题

来源：AcWing03 - 完全背包问题 - https://www.acwing.com/problem/content/description/3/

有 $N$ 种物品和一个容量是 $V$ 的背包，每种物品都有无限件可用。

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

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

输入格式

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

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

输出格式

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

数据范围

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

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例

10

分析

状态表示

集合：满足“在前 $i$ 个物品选择，总体积 $<j$ ”的条件的所有选法的集合。
属性：集合中选法价值的最大值。

综上，状态表示为：

$dp(i,j):=$ 从第 $1\sim i$ 个物品中选取，总体积 $<j$ 时，能取到的物品的最大总价值。

状态计算

集合划分：

$dp(i,j)$ 可划分为：

划分	结果
从 $1\sim i$ 个物品选取，总体积 $<j$ ，且选 $0$ 个第 $i$ 个物品的选法。	$dp(i-1,j)$
从 $1\sim i$ 个物品选取，总体积 $<j$ ，且选 $1$ 个第 $i$ 个物品的选法。	$dp(i-1,j-1\times v_i)+1\times w_i$
从 $1\sim i$ 个物品选取，总体积 $<j$ ，且选 $2$ 个第 $i$ 个物品的选法。	$dp(i-1,j-2\times v_i)+2\times w_i$
$\cdots\cdots$	$\cdots\cdots$
从 $1\sim i$ 个物品选取，总体积 $<j$ ，且选 $k$ 个第 $i$ 个物品的选法。$(k\leq j/v_i)$	$dp(i-1,j-k\times v_i)+k\times w_i$

这 $k+1$ 种情况的结果合并为一个式子：$dp(i-1,j-k\times v_i)+k\times w_i\ (k\in\mathbb{Z},且k\leq j/v_i)$

因此，$dp(i,j)$ 的值就是 $k+1$ 个划分中的最大值。

代码

朴素版本

时间复杂度：$O(N\cdot V^2)$ (最坏情况)
空间复杂度：$O(N\cdot V)$

#include <iostream>
#include <algorithm>

using namespace std;

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

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

时间优化

$$ \begin{align} dp(i,j)&=\max\left\{dp(i-1,j),dp(i-1,j-1\times v_i)+1\times w_i,\cdots,dp(i-1,j-k\times v_i)+k\times w_i\right\}\\ dp(i,j-v_i)&=\max\left\{dp(i-1,j-1\times v_i)+0\times w_i,\cdots,dp(i-1,j-k\times v_i)+(k-1)\times w_i\right\}\\ &\Rightarrow dp(i,j)=\max\left\{dp(i-1,j),dp(i,j-v_i)+w_i\right\} \end{align} $$

通过观察 $dp[i][j]$ 与 $dp[i][j-v[i]]$，发现有很多相似元素，每个元素只相差 $w[i]$，因此 $dp[i][j]$ 无需第三次循环即可得到结果。

时间复杂度：$O(N\cdot V)$
空间复杂度：$O(N\cdot V)$

#include <iostream>
#include <algorithm>

using namespace std;

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

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

空间优化

思想和上面的 01 背包一模一样。但此处不能反向循环，得正向循环，因为 $dp[i][j]$ 使用的都是同层的数据，正向可以取到正确数据，反向的话就取到了上一层 dp 的数据。

时间复杂度：$O(N\cdot V)$
空间复杂度：$O(V)$

#include <iostream>
#include <algorithm>

using namespace std;

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

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

算法 | 动态规划背包模型 - A

01 背包模型

例题

输入格式

输出格式

数据范围

输入样例

输出样例

分析

状态表示

状态计算

代码

朴素版本

空间优化

完全背包模型

例题

输入格式

输出格式

数据范围

输入样例

输出样例

分析

状态表示

状态计算

代码

朴素版本

时间优化

空间优化

添加新评论

最新文章

分类

标签

其它