算法日记25：01背包（DFS-＞记忆化搜索-＞倒叙DP-＞顺序DP-＞空间优化）
- 对于01背包这类DP入门的问题，新手应该是去了解如何一步步得出所谓的状态转移方程，而不是直接去看答案所给予的方程
- 过程应该为：DFS->记忆化搜索->倒序递推->循序递推->二维->一维
一、DFS暴力搜索 O ( 2 n ) O(2^n) O(2n)
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);//从第一件物品开始，当前剩余容量为v
cout << 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 ) O(N*V) 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 ) O(N*V) 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 i 的状态 − > -> −> i − 1 i-1 i−1的状态
- 而物品
i的状态此时表明已经遍历过了，也就是已经选过了，那么此时就变成了从这个物品已经选过的状态—>下一个状态 - 那么此时，这个物品就重复选了！！！，这就变成了完全背包！！！（也就是物品的数量无限）
2、但是如果是逆序的话，那么就会从 i − 1 — > i − 1 的状态 i-1—>i-1的状态 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;
}
总结：
