算法日记25：01背包（DFS-＞记忆化搜索-＞倒叙DP-＞顺序DP-＞空间优化）

在这里插入图片描述

对于01背包这类DP入门的问题，新手应该是去了解如何一步步得出所谓的状态转移方程，而不是直接去看答案所给予的方程
过程应该为：DFS->记忆化搜索->倒序递推->循序递推->二维->一维

一、DFS暴力搜索 $O(2^n)$

1.1：思路讲解：

无需多说，最暴力的做法
最经典的指数级枚举(每个物品选/不选)

1.2：代码解析：

#include <bits/stdc++.h>
using namespace std;const int N = 1007;
int vi[N],wi[N];
int n, v;int dfs(int x, int Spv)//从第x件物品开始，当前剩余容量为Spv
{if (x > n) return 0;if (Spv < vi[x])    //容量不够拿不了{return dfs(x + 1, Spv);}else //表明容量够{return max(dfs(x + 1, Spv), dfs(x + 1, Spv - vi[x]) + wi[x]); //不拿/拿}
}void solve()
{cin >> n >> v;for (int i = 1; i <= n; i++){cin >> vi[i]>>wi[i];}int res=dfs(1, v);//从第一件物品开始，当前剩余容量为vcout << res <<'\n';
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _ =1; //cin >> _;while (_--) solve();system("pause");return 0;
}

对于暴力来说，只要样例大于20，一般都会超时

二、记忆化搜索： $O (N * V)$

2.1：思路讲解：

1、相比所谓的暴力搜索，优化了大量的时间复杂度（指数级->线性级）
2、所谓记忆化搜索，就是把DFS计算过的数据不再重复计算（用一个mem数组存储状态）
PS ：记忆化数组的数据个数一般和DFS函数的参数一致

2.2：代码解析：

#include <bits/stdc++.h>
using namespace std;const int N = 1007;
int vi[N],wi[N];
int n, v;
int mem[N][N];
int f[N];int dfs(int x, int SpV)//从第x件物品开始，当前剩余容量为Spv
{if(mem[x][SpV]) return mem[x][SpV];if(x>n) return 0;   //表示已经拿完了if(SpV>=vi[x]) //能够拿这个物品{//此时，考虑 不拿/拿return  mem[x][SpV]=max(dfs(x+1,SpV),dfs(x+1,SpV-vi[x])+wi[x]);}        else //不能拿{return mem[x][SpV]=dfs(x+1,SpV);}
}void solve()
{cin >> n >> v;for (int i = 1; i <= n; i++){cin >> vi[i]>>wi[i];}cout<<dfs(1,v)<<'\n';}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _ =1; //cin >> _;while (_--) solve();system("pause");return 0;
}

三、倒序动态规划 $O (N * V)$

3.1：思路讲解

1、典型的空间换时间的做法，相比于搜索，节约了大量的时间复杂度
2、动态规划的for循环变量的遍历应该与DFS边界的限制的参数相同（例如：本题目中，边界与物品数量X、剩余的体积SPV有关）所以循环为n/v作为参数
3、因为在递归中，只有归才是产生答案的过程，所以可以从边界直接开始推出答案

3.2：代码解析

#include <bits/stdc++.h>
using namespace std;const int N = 1007;
int vi[N],wi[N];
int n, v;
int mem[N][N];
int f[N][N];// int dfs(int x, int Spv)//从第x件物品开始，当前剩余容量为Spv
// {
//     if (mem[x][Spv]) return mem[x][Spv];//     int sum = 0;
//     if (x > n) sum= 0;//     else if (Spv < vi[x])    //容量不够拿不了
//     {
//         sum=dfs(x + 1, Spv);
//     }
//     else //表明容量够
//     {
//         sum = max(dfs(x + 1, Spv), dfs(x + 1, Spv - vi[x]) + wi[x]); //不拿/拿
//     }
//     mem[x][Spv] = sum;
//     return mem[x][Spv];
// }void solve()
{cin >> n >> v;for (int i = 1; i <= n; i++){cin >> vi[i]>>wi[i];}for (int i = 1; i <= n; i++){for (int j = 0; j <= v; j++){if (j < vi[i])  //当前剩余容量<物品容量{f[i][j] = f[i - 1][j];} else   //表明容量够{f[i][j] = max(f[i - 1][j], f[i - 1][j - vi[i]] + wi[i]);  //拿/不拿}}}cout << f[n][v] <<'\n';
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _ =1; //cin >> _;while (_--) solve();system("pause");return 0;
}

四、顺序动态规划：

4.1：思路讲解：

1、倒序遍历物品总是怪怪的，那么可不可以正序枚举呢，当然是可以的。
2、此时，状态转移方程与DFS搜索的方程保持一致
PS：正序枚举相当于以n->1开始递归，此时边界刚刚好是为1，所以循环从1开始

4.2：代码解析：

#include <bits/stdc++.h>
using namespace std;const int N = 1007;
int vi[N],wi[N];
int n, v;
int mem[N][N];
int f[N][N];// int dfs(int x, int Spv)//从第x件物品开始，当前剩余容量为Spv
// {
//     if (mem[x][Spv]) return mem[x][Spv];//     int sum = 0;
//     if (x > n) sum= 0;//     else if (Spv < vi[x])    //容量不够拿不了
//     {
//         sum=dfs(x + 1, Spv);
//     }
//     else //表明容量够
//     {
//         sum = max(dfs(x + 1, Spv), dfs(x + 1, Spv - vi[x]) + wi[x]); //不拿/拿
//     }
//     mem[x][Spv] = sum;
//     return mem[x][Spv];
// }void solve()
{cin >> n >> v;for (int i = 1; i <= n; i++){cin >> vi[i]>>wi[i];}for (int i = 1; i <= n; i++){for (int j = 0; j <= v; j++){if (j < vi[i])  //当前剩余容量<物品容量{f[i][j] = f[i - 1][j];} else   //表明容量够{f[i][j] = max(f[i - 1][j], f[i - 1][j - vi[i]] + wi[i]);  //拿/不拿}}}cout << f[n][v] <<'\n';
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _ =1; //cin >> _;while (_--) solve();system("pause");return 0;
}

五、二维 -> 一维：

5.1：思路讲解（为什么要逆序枚举体积？？）

1、注意01背包的二维的遍历应该的逆序，为什么呢？

看下图，如果是正序的话，那么结果就会从 $i$ 的状态 $- >$ $i - 1$ 的状态
而物品 i 的状态此时表明已经遍历过了，也就是已经选过了，那么此时就变成了从这个物品已经选过的状态—>下一个状态
那么此时，这个物品就重复选了！！！，这就变成了完全背包！！！（也就是物品的数量无限）

2、但是如果是逆序的话，那么就会从 $i - 1— > i - 1 的状态$

表明此时的状态为，没选过的状态—>下一个状态
那么此时，就会使得状态转移为：还没选过这个物品的情况->更新*还没选过这个物品的情况
这就符合01背包的背景！！！故01背包应该逆序

5.2：代码解析：

#include <bits/stdc++.h>
using namespace std;const int N = 1007;
int vi[N],wi[N];
int n, v;
int mem[N][N];
int f[N];// int dfs(int x, int Spv)//从第x件物品开始，当前剩余容量为Spv
// {
//     if (mem[x][Spv]) return mem[x][Spv];//     int sum = 0;
//     if (x > n) sum= 0;//     else if (Spv < vi[x])    //容量不够拿不了
//     {
//         sum=dfs(x + 1, Spv);
//     }
//     else //表明容量够
//     {
//         sum = max(dfs(x + 1, Spv), dfs(x + 1, Spv - vi[x]) + wi[x]); //不拿/拿
//     }
//     mem[x][Spv] = sum;
//     return mem[x][Spv];
// }void solve()
{cin >> n >> v;for (int i = 1; i <= n; i++){cin >> vi[i]>>wi[i];}for (int i = 1; i <= n; i++){for (int j = v; j >= 0; j--){if(j>=vi[i]) f[j] = max(f[j], f[j - vi[i]] + wi[i]);  //拿/不拿}}cout << f[v] <<'\n';
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _ =1; //cin >> _;while (_--) solve();system("pause");return 0;
}