简介
动态规划（Dynamic Programming, DP）及其解决的问题、根据其设计的算法及优化。
动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
由于动态规划并不是某种具体的算法，而是一种解决特定问题的方法，因此它会出现在各式各样的数据结构中，与之相关的题目种类也更为繁杂。
在 \(OI\) 中，计数等非最优化问题的递推解法也常被不规范地称作 DP，因此本章将它们一并列出。事实上，动态规划与其它类型的递推的确有很多相似之处，学习时可以注意它们之间的异同。
背景
\(DP\) 是信奥中十分重要的一部分，基本上就是 \(csp−j\) 考 \(DP\)，\(csp−s\) 考 \(DP\), \(NOIP\) 考 \(DP\), \(NOI\)还是考 \(DP\)。并且，万物皆可 \(DP\)。
所以学好 \(DP\) 是学好信息学奥赛，打好各类比赛的基础!
而背包作为 \(DP\) 的基础，自然是重中之重。
这篇文章主要讲的是背包的思想和各种背包的实现
01背包
首先，我们来看二维的 \(01\) 背包。
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
题目描述:
有 \(N\) 件物品和一个容量为 \(V\) 的背包。第 \(i\) 件物品的费用是 \(v_i\)，价值是 \(w_i\)。求解将哪些物品装入背包可使价值总和最大。
数组定义： \(dp[maxn][maxV]\)
初始化：\(dp\) 数组全部赋值成 \(0\)
状态转移方程：
用子问题定义状态：即 \(dp[i][j]\) 表示前 \(i\) 件物品恰放入一个容量为 \(j\) 的背包可以获得的最大价值。则其状态转移方程便是:
\(dp[i][j] = max(dp[i − 1][j], dp[i − 1][j − w[i]]+v[i])\)
输出： \(printf("\%d", dp[n][V])\)
代码：
for(int i=1;i<=n;++i)
for(int j=0;j<=V;++j)
if (v[i]>j) dp[i][j]=dp[i-1][j];
else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
接着我们进行优化
以上方法的时间和空间复杂度均为 \(O(Vn)\)，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到 \(O(V)\)。
先考虑上面讲的基本思路如何实现。
肯定是有一个主循环 \(i = 1..N\)，每次算出来二维数组 \(dp[i][0..V]\) 的所有值。
那么，如果只用一个数组 \(dp[0..V]\)，能不能保证第 \(i\) 次循环结束后 \(dp[v]\) 中表示的就是我们定义的状态 \(dp[i][j]\) 呢？
\(dp[i][j]\) 是由 \(dp[i − 1][j]\) 和 \(dp[i − 1][j − w[i]]\) 两个子问题递推而来，能否保证在推 \(dp[i][j]\) 时（即在第 \(i\) 次主循环中推 \(dp[j]\) 时）能够得到 \(dp[i − 1][j]\) 和 \(dp[i − 1][j − w[i]]\) 的值呢？
事实上，这要求在每次主循环中我们以 \(j = V..0\) 的顺序推 \(dp[j]\)，这样才能保证推 \(dp[j]\) 时 \(f[j − v[i]]\) 保存的是状态 \(f[i − 1][j − w[i]]\) 的值。
因此，\(dp\) 数组就可以从两维变为一维，变成 \(dp[maxV]\);
状态转移方程：
\(dp[j] = max(dp[j], dp[j − w[i]] + v[i])\)
这样，核心代码就变成了
for(int i=1;i<=n;++i)
for(j=V;j>=v[i];--j)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
动态规划原理
能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。
最优子结构
具有最优子结构也可能是适合用贪心的方法求解。
注意要确保我们考察了最优解中用到的所有子问题。
- 证明问题最优解的第一个组成部分是做出一个选择；
- 对于一个给定问题，在其可能的第一步选择中，假定你已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择；
- 给定可获得的最优解的选择后，确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间；
- 证明作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。方法是反证法，考虑加入某个子问题的解不是其自身的最优解，那么就可以从原问题的解中该子问题的最优解替换掉当前的非最优解，从而得到原问题的一个更优的解，从而与原问题最优解的假设矛盾。
要保持子问题空间尽量简单，只在必要时扩展。
最优子结构的不同体现在两个方面：
- 原问题的最优解中涉及多少个子问题；
- 确定最优解使用哪些子问题时，需要考察多少种选择。
子问题图中每个定点对应一个子问题，而需要考察的选择对应关联至子问题顶点的边。
无后效性
已经求解的子问题，不会再受到后续决策的影响。
子问题重叠
如果有大量的重叠子问题，我们可以用空间将这些子问题的解存储下来，避免重复求解相同的子问题，从而提升效率。
基本思路
对于一个能用动态规划解决的问题，一般采用如下思路解决：
- 将原问题划分为若干 阶段，每个阶段对应若干个子问题，提取这些子问题的特征（称之为 状态）；
- 寻找每一个状态的可能 决策，或者说是各状态间的相互转移方式（用数学的语言描述就是 状态转移方程）。
- 按顺序求解每一个阶段的问题。
A. 我的眼睛就是尺
时间：1s 空间：256M
题目描述
“就这速度我也能滑出来” “他是指定进不了下一轮的” “我的眼睛就是尺” 这是王濛在解说冬奥会时的精彩语录。今天你也来展示一下什么叫做眼睛就是尺，你有 \(n\) 个东西，你一眼就能看出来他们有多重（因为上面写了重多少斤），让你选几个东西，使得他们的总重量在不小于t的情况下，尽可能地接近 \(t\)，求出这个最小的总重量。如果不存在则输出 \(-1\)。
输入格式
第一行两个整数 \(n,t\)
第二行 \(n\) 个整数，第 \(i\) 个整数代表第 \(i\) 件物品的重量
输出格式
一个整数.
样例输入
3 30
25
10
23
样例输出
33
约定
\(1 \le n \le 50\), \(1 \le t \le 10000\), \(1 \le a_i \le 10000\)
点击查看代码
#include<iostream>
#include<string.h>
using namespace std;
int n, t, a[60];
long long sum = 0, ans = 0x3f3f3f3f;
void dfs(int now, long long res) {
if(now > n) return;
if(res >= t) {
ans = min(ans, res);
return;
}
dfs(now + 1, res);
dfs(now + 1, res + a[now]);
return;
}
int main() {
cin >> n >> t;
for(int i = 1; i <= n; i ++) {
cin >> a[i];
sum += a[i];
}
if(sum < t) {
cout << "-1\n";
return 0;
}
dfs(1, 0);
cout << ans << endl;
return 0;
}
编译结果
compiled successfully
time: 9ms, memory: 3500kb, score: 100, status: Accepted
> test 1: time: 1ms, memory: 3392kb, points: 10, status: Accepted
> test 2: time: 1ms, memory: 3428kb, points: 10, status: Accepted
> test 3: time: 0ms, memory: 3500kb, points: 10, status: Accepted
> test 4: time: 1ms, memory: 3340kb, points: 10, status: Accepted
> test 5: time: 1ms, memory: 3404kb, points: 10, status: Accepted
> test 6: time: 1ms, memory: 3352kb, points: 10, status: Accepted
> test 7: time: 1ms, memory: 3388kb, points: 10, status: Accepted
> test 8: time: 1ms, memory: 3444kb, points: 10, status: Accepted
> test 9: time: 1ms, memory: 3352kb, points: 10, status: Accepted
> test 10: time: 1ms, memory: 3384kb, points: 10, status: Accepted
不同点：
这道题我们需要求出体积至少为 \(j\) 的最小价值
初始化： \(dp[0][0] = 0\), \(dp[0][1…t] = inf\)
状态转移方程： \(dp[i][j] = min(dp[i − 1][j], dp[i − 1][max(0, j − w[i])] + v[i])\)
拓展：
需要求体积至少为 \(j\) 的方案数
初始化： \(dp[0][0] = 1\), \(dp[0][1…t] = 0\)
状态转移方程： \(dp[i][j] = dp[i − 1][j] + dp[i − 1][max(0, j − w[i])]\)
恰好为 j
\(（1）\) 恰好为 \(j\) 的最小价值；
\(（2）\) 恰好为 \(j\) 的最大价值；
\(（3）\) 恰好为 \(j\) 的方案数；
解法： 与原本的 \(01\) 背包相同，初始化不同
初始化： \(dp[0][0] = 0\), \(dp[0][1…t] = −1 / inf\)
B. we are 伐木累
时间：1s 空间：256M
题目描述
光头强强是个伐木工人，有天他趁着熊三和熊四不在，又来砍树啦！
他现在把一棵高为n的树砍倒了，但因为树太大了实在不好搬，所以他打算把这棵树砍成若干段。而他的老板是有要求的，只收长度为a或者长度为b或者长度为c的三种型号的木段，现在他希望最后得到的木段的数量尽可能的多。光头强强是个节俭的人，所以他希望树恰好被分完，不能有剩余边角料，如果不能分完则输出0。
输入格式
一行四个整数 \(n,a,b,c\) \(（1 \le n,a,b,c \le 1000000）\)
输出格式
一个整数代表木段数量的最大值。
样例输入
5 5 3 2
样例输出
2
点击查看代码
#include<iostream>
#include<string.h>
using namespace std;
int n, a, b, c;
int dp[1000005];
int main() {
cin >> n >> a >> b >> c;
dp[0] = 0;
for (int i = 1; i <= n; i++) {
dp[i] = -1;
if (i >= a && dp[i - a] != -1) dp[i] = max(dp[i], dp[i - a] + 1);
if (i >= b && dp[i - b] != -1) dp[i] = max(dp[i], dp[i - b] + 1);
if (i >= c && dp[i - c] != -1) dp[i] = max(dp[i], dp[i - c] + 1);
}
if(dp[n] < 0) cout << 0 << endl;
else cout << dp[n] << endl;
return 0;
}
编译结果
compiled successfully
time: 17ms, memory: 7280kb, score: 100, status: Accepted
> test 1: time: 0ms, memory: 3432kb, points: 10, status: Accepted
> test 2: time: 1ms, memory: 3468kb, points: 10, status: Accepted
> test 3: time: 1ms, memory: 3348kb, points: 10, status: Accepted
> test 4: time: 0ms, memory: 3436kb, points: 10, status: Accepted
> test 5: time: 0ms, memory: 3448kb, points: 10, status: Accepted
> test 6: time: 1ms, memory: 3400kb, points: 10, status: Accepted
> test 7: time: 0ms, memory: 3252kb, points: 10, status: Accepted
> test 8: time: 5ms, memory: 6444kb, points: 10, status: Accepted
> test 9: time: 3ms, memory: 6848kb, points: 10, status: Accepted
> test 10: time: 6ms, memory: 7280kb, points: 10, status: Accepted
C. 宝物筛选
题目描述：
终于，破解了千年的难题。小 \(F\) 找到了王室的宝物室，里面堆满了无数价值连城的宝物。
这下小 \(F\) 可发财了，嘎嘎。但是这里的宝物实在是太多了，小 \(F\) 的采集车似乎装不下那么多宝物。看来小 \(F\) 只能含泪舍弃其中的一部分宝物了。
小 \(F\) 对洞穴里的宝物进行了整理，他发现每样宝物都有一件或者多件。他粗略估算了下每样宝物的价值，之后开始了宝物筛选工作：小 \(F\) 有一个最大载重为 \(W\) 的采集车，洞穴里总共有 \(n\) 种宝物，每种宝物的价值为 \(v_i\)，重量为 \(w_i\)，每种宝物有 \(m_i\) 件。小 \(F\) 希望在采集车不超载的前提下，选择一些宝物装进采集车，使得它们的价值和最大。
输入格式：
第一行为一个整数 \(n\) 和 \(W\)，分别表示宝物种数和采集车的最大载重。
接下来 \(n\) 行每行三个整数 \(v_i\), \(w_i\), \(m_i\)。
输出格式：
输出仅一个整数，表示在采集车不超载的情况下收集的宝物的最大价值。
样例输入：
4 20
3 9 3
5 9 1
9 4 2
8 1 3
样例输出：
47
数据规模：
对于 \(100\%\) 的数据，\(n \le ∑m_i \le 10 ^ 5\)，\(0 \le W \le 4 × 10 ^ 4\)，\(1 \le n \le 100\)。
点击查看代码
#include<iostream>
#include<cstdio>
using namespace std;
int n, m;
int num, cnt, ans, f[100005], v[1000005], w[1000005];
int main() {
scanf("%d %d", &n, &m);
for(int i=1, x, y, z; i <= n; i++) {
scanf("%d %d %d", &x, &y, &z);
num = 1;
while(z >= num) {
z -= num;
cnt++;
v[cnt] = num * x;
w[cnt] = num * y;
num *= 2;
}
cnt++;
v[cnt] = z * x;
w[cnt] = z * y;
}
for(int i = 1; i <= cnt; i++)
for(int j = m; j >= w[i]; j--)
f[j] = max(f[j], f[j - w[i]] + v[i]);
for(int j = 0; j <= m; j++) ans = max(ans, f[j]);
printf("%d", ans);
return 0;
}
编译结果
compiled successfully
time: 69ms, memory: 5820kb, score: 100, status: Accepted
> test 1: time: 9ms, memory: 5768kb, points: 10, status: Accepted
> test 2: time: 0ms, memory: 5748kb, points: 10, status: Accepted
> test 3: time: 1ms, memory: 5652kb, points: 10, status: Accepted
> test 4: time: 16ms, memory: 5784kb, points: 10, status: Accepted
> test 5: time: 15ms, memory: 5796kb, points: 10, status: Accepted
> test 6: time: 16ms, memory: 5612kb, points: 10, status: Accepted
> test 7: time: 0ms, memory: 5628kb, points: 10, status: Accepted
> test 8: time: 3ms, memory: 5636kb, points: 10, status: Accepted
> test 9: time: 8ms, memory: 5820kb, points: 10, status: Accepted
> test 10: time: 1ms, memory: 5664kb, points: 10, status: Accepted
D. 学习king
时间：1s 空间：512M
题目描述：
众所周知，期末考试是一件非常恐怖的事情，比如 \(Bob\) 马上期末考试，而他因为玩原神过于入迷，导致他学了但又好像啥都没学。他不想摆烂，所以打算奋起直追，他还有 \(N\) 门课需要去复习(预习)，但现在距离期末测试只有 \(M\) 天了。根据不同的复习策略，分配各科的复习时间，最后获得的效果也不同，问他应如何安排，使得最终能够取得最好的复习效果呢？
输入格式：
第一行两个整数 \(N,M\) ,分别代表还有 \(N\) 门课要复习和剩下 \(M\) 天。
接下来 \(N\) 行 \(M\) 列整数，第 \(i\) 行第 \(j\) 列记作 \(c[i][j]\) ，代表第 \(i\) 门课，如果 \(Bob\) 花 \(j\) 天学习，可以取得的效果。
输出格式：
一行一个整数代表 \(Bob\) 可以获得的效果最大值。
样例1输入：
2 2
1 2
1 4
样例1输出：
4
约定与提示： \(1 \le N,M \le 200\)
点击查看代码
#include<iostream>
#include<string.h>
using namespace std;
int n, m, a[205][205], dp[205][205];
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
cin >> a[i][j];
for(int i = 1; i <= n; i ++) {
for(int j = 0; j <= m; j ++) {
dp[i][j] = dp[i - 1][j];
for(int k = 1; k <= j; k ++) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - k] + a[i][k]);
}
}
}
cout << dp[n][m] << endl;
return 0;
}
编译结果
compiled successfully
time: 22ms, memory: 3848kb, score: 100, status: Accepted
> test 1: time: 0ms, memory: 3508kb, points: 10, status: Accepted
> test 2: time: 0ms, memory: 3436kb, points: 10, status: Accepted
> test 3: time: 1ms, memory: 3420kb, points: 10, status: Accepted
> test 4: time: 1ms, memory: 3520kb, points: 10, status: Accepted
> test 5: time: 1ms, memory: 3576kb, points: 10, status: Accepted
> test 6: time: 1ms, memory: 3516kb, points: 10, status: Accepted
> test 7: time: 5ms, memory: 3680kb, points: 10, status: Accepted
> test 8: time: 2ms, memory: 3716kb, points: 10, status: Accepted
> test 9: time: 3ms, memory: 3540kb, points: 10, status: Accepted
> test 10: time: 8ms, memory: 3848kb, points: 10, status: Accepted