通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(分治)的方式去解决:动态规划 (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;
}

标签: 动态规划

添加新评论