简介

动态规划常用于最优化或计数问题，通常要满足最优子结构（一个问题的答案可以由其子问题答案算出），无后效性（可以按某种顺序求解），子问题的重叠性（递归时可能会走到相同子问题）。

使用递归实现就是记忆化搜索，而如果我们能确定转移顺序那么我们就可以按顺序转移。

这一类问题通常考察思维，所以极其令我厌恶，通常是先设计一个状态，再想状态之间的转移，然后再优化。

背包

通常的问题形式是：

有 nn 类物品，物品有体积 vv，有价值 ww，需要满足一定限制的条件下选择物品是的价值和最大。大多数题目的限制都是提及综合不超过 mm。

01 背包

这个背包的特殊之处在于每类物品只有一个。

为了防止一个物品多次选择，我们采用 从大到小枚举容积 的方式做。

转移方程明显为 fi,j←max⁡(fi−1,j−v[i]+w)f_{i,j}\leftarrow \max (f_{i-1,j-v[i]}+w)，可滚。

完全背包

这种背包每类物品有无限个，这样就不用关心一个物品是否多次重复选择，我们容许多次选择，那么可以 从小到大枚举容积。

转移方程不变，可滚。

一种非常简单的优化是如果有 vi≥vjv_i\geq v_j 且 wi≤wjw_i\leq w_j，那么可以把种类 ii 踢掉。那么一种更为简单的方式是，对于 vv 相等的几类物品，只留下 ww 最大的物品即可。

多重背包

这种背包每种物品的物品有 kk 个。

首先可以二进制分组，把 kk 拆分为 20+⋯+2p+q2^0+\cdots+2^p+q 的形式，前面 22 的几个幂就可以配出 1∼k−q1\sim k-q 的所有情况，加上 qq 就能配出 1∼k1\sim k 的所有情况了，总物品数是 O(log⁡k)O(\log k) 的，然后进行 01 背包。

也可以使用单调队列优化，此处先不提。

二维费用背包

多开一维记录状态即可。

分组背包

首先遍历每一组，内部首先从大到小枚举容量，再遍历每组中每个物品；外部遍历每个组即可。

板子题：P1757

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// Problem: P1757 通天之分组背包
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1757
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Start coding at 2024-01-03 20:11:30
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<pair<int,int> > v[101];
int a,b,k,ans;
int dp[1001];
int main(){
	ios::sync_with_stdio(0);
	cin>>m>>n;
	for(int i=1;i<=n;i++)cin>>a>>b>>k,v[k].push_back(make_pair(a,b));
	for(int i=0;i<=100;i++){
		for(int j=m;j>=0;j--){
			for(auto p:v[i]){
				if(j>=p.first)dp[j]=max(dp[j],dp[j-p.first]+p.second),ans=max(ans,dp[j]);
			}
		}
	}
	cout<<ans;
	return 0;
}

例题

P4141 消失之物

考虑 01 背包没有对顺序的要求，所以每次都可以把现在要撤销的贡献都当成最后一次加入的，那么可以直接撤销。转移方程式：fi=fi+fi−w[j]f_i=f_i+f_{i-w[j]}。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// Problem: P4141 消失之物
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4141
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Start coding at 2024-01-03 20:43:35
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int w[10001];
int dp[10001]={1};
int cnt[10001];
signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>w[i];
	for(int i=1;i<=n;i++){
		for(int j=m;j>=w[i];j--){
			dp[j]+=dp[j-w[i]];
			dp[j]%=10;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++)cnt[j]=dp[j];
		for(int j=w[i];j<=m;j++)cnt[j]-=cnt[j-w[i]];
		for(int j=1;j<=m;j++)cout<<(cnt[j]%10+10)%10;
		cout<<"\n";
	}
	return 0;
}