通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（分治）的方式去解决：动态规划 (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<N,V\le 1000$
$0<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\{dp(i-1,j),dp(i-1,j-v_i)+w_i\}$

解析：

如果在第 $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<N,V\le 1000$
$0<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\le 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},\mathrm{且}k\le 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{array}{rl}dp(i,j)& =max\{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\}\\ dp(i,j-v_i)& =max\{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\}\\ & \Rightarrow dp(i,j)=max\{dp(i-1,j),dp(i,j-v_i)+w_i\}\end{array}$$

通过观察 $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;
}