作为菜到不行的苣蒻，要从暴搜过渡到记忆化再过渡到动态规划简直是一件难到不行的事。以至于我的dp题单全是记忆化搜索过的。现在我通过洛谷P1048 采药来理解一下动归以及记忆化搜索的关系。
搜索
暴搜/$604.00KB$/$8.41s$
首先，作为菜到不行的苣蒻Tim，第一个想到的当然是暴搜，就不讲解了，基础的dfs
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
| #include<bits/stdc++.h>
#define MAXN 105
using namespace std;
int n,T,t[MAXN],v[MAXN],tot,ans = -1;
void dfs(int x){
if(x > n||T == 0){
ans = max(ans,tot);
return;
}
if(t[x] <= T){
tot += v[x],T -= t[x];
dfs(x+1);
tot -= v[x],T += t[x];
}
dfs(x+1);
}
int main(){
cin>>T>>n;
for(int i = 1;i <= n;i++)
cin>>t[i]>>v[i];
dfs(1);
cout<<ans<<endl;
return 0;
}
|
当你提交上去，你会看到：完美的三十分和7个$TLE$
一看数据范围:
对于$30%$的数据,$M\le 10$
对于全部的数据,$M\le 100$
啊这……
记忆化搜索/$1016.00KB$/$47ms$
于是，我们开始了记忆化搜索的道路:
将dfs的参数扩展成两个，并给出int返回值:int dfs(int x,int ti)，$x$表示第$x$件物品，$ti$表示还剩余$ti$时间。
通过$mem[x][ti]$数组存储第$x$到$n$个物品在剩下$ti$时间时能拿到的最多的价值。
于是，我们容易得出，当第$x$个物品可以取时，也就是说$ti\ge t[x]$时，我们可以有两种方案，取和不取，也就是$dfs(x+1,ti-t[x]) + v[x]$（取），$dfs(x+1,ti)$(不取)，比较这两个的大小，取$max$就好了；如果$ti<t[x]$，我们就取不了第$x$件物品，于是我们需要$dfs(x+1,ti)$。
我们返回的边界条件是$x > n$（超出物品个数）和$ti == 0$（没时间了），我们就返回$mem[x][ti] = 0$（取不到东西）
记得初始化$mem$数组为$-1$
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
| #include<bits/stdc++.h>
#define MAXN 105
#define MAXT 1005
using namespace std;
int n,T,t[MAXN],v[MAXN],mem[MAXN][MAXT];
int dfs(int x,int ti){
if(mem[x][ti] != -1) return mem[x][ti];
if(x > n||ti==0) return mem[x][ti] = 0;
int dfs1 = -1;
if(t[x] <= ti) dfs1 = dfs(x+1,ti-t[x]) + v[x];
return mem[x][T] = max(dfs1,dfs(x+1));
}
int main(){
cin>>T>>n;
for(int i = 1;i <= n;i++)
cin>>t[i]>>v[i];
memset(mem,-1,sizeof(mem));
cout<<dfs(1,T)<<endl;
return 0;
}
|
当你提交上去时，你神奇的发现，AC了！其实这是因为记忆化搜索的时间复杂度和动态规划的时间复杂度差不太多，因为对于记忆化搜索来说，一条路也只会走一次，只不过是用的递归，但不至于$TLE$
将dfs转化成dp
我们dfs的方程是什么？
也就是：
Holy Shit!这不就是状态转移方程？
动态规划(0/1背包)
二维dp/$1016.00KB$/$32ms$
边界条件还是一样的：当$ti < t[x]$，$dp[x][ti] = dp[x+1][ti]$;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include<bits/stdc++.h>
#define MAXN 105
#define MAXT 1005
using namespace std;
int n,T,t[MAXN],v[MAXN],dp[MAXN][MAXT];
int main(){
cin>>T>>n;
for(int i = 1;i <= n;i++)
cin>>t[i]>>v[i];
for(int ti = 1;ti <= T;ti++)
for(int x = n;x >= 1;x--)
if(ti < t[x]) dp[x][ti] = dp[x+1][ti];
else dp[x][ti] = max(dp[x+1][ti-t[x]]+v[x],dp[x+1][ti]);
cout<<dp[1][T]<<endl;
return 0;
}
|
将二维dp转化为一维dp
分析我们的dp数组，不难发现，每一个$ti$都对应了$n$个物品的收益，而我们只需要最大的那个收益。
我们只需要分析当第$x$件物品可以取时，取是最大值还是不取是最大值。
怎么表示呢？很明显，当时间为$ti$时，我们要是取第$x$件物品，那么我们的收益最大值就是当时间为$ti-t[x]$的最大收益加上$v[x]$,所以我们很容易得到转移方程:
但是，我们要注意，如果我们正着dp，也就是从$ti = 0$dp到$ti = n$，这样有可能会重复，也就是比如我们$dp[6]$取了第$x$件物品，到后面如果转移到$ti = 6$时（$dp[6] + v[x]$），我们就会重复计算$v[x]$，从$ti = n$dp到$ti = 0$就不会出现这个问题（$ti$小的不会转移到$ti$大的）
而且我们只需要dp$ti \ge t[x]$，因为当$ti < t[x]$时，我们的转移$dp[ti-t[x]]$会溢出,因为我们根本取不了$x$。
一维dp/$632.00KB$/$41ms$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include<bits/stdc++.h>
#define MAXN 105
#define MAXT 1005
using namespace std;
int n,T,t[MAXN],v[MAXN],dp[MAXT];
int main(){
cin>>T>>n;
for(int i = 1;i <= n;i++)
cin>>t[i]>>v[i];
for(int x = 1;x <= n;x++)
for(int ti = T;ti >= t[x];ti--)
dp[ti] = max((dp[ti-t[x]]+v[x]),dp[ti]);
cout<<dp[T]<<endl;
return 0;
}
|
