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

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

1.1）思路解析

1、注意和01背包的区别在于每个物品可以无限次选择

• 注意在完全背包中，当一个物品被选择过一次，我们仍然需要考虑是否继续选择这个物品
  • 01背包： max(dfs(x + 1, Spv), dfs(x + 1, Spv - vi[x]) + wi[x])//不选/选
  • 完全背包：max(dfs(x+1,Spv),dfs(x,Spv-vi[x])+wi[x]) //不选/选

2、注意当选这个物品的时候，下一次应该继续考虑这个物品是否继续选择，所以是dfs(x,Spv-vi[x])+wi[x]

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,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);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;
}

二、记忆化搜索$O(n\ast 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 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,Spv-vi[x])+wi[x],dfs(x+1,Spv));}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;
}

三、倒序动态规划

3.1）思路解析

1、典型的空间换时间的做法，相比于搜索，节约了大量的时间复杂度

2、动态规划的for循环变量的参数，应该与DFS边界的限制的参数相同（例如：本题目中，边界与物品数量X、剩余的体积SPV有关）所以循环为n/v作为参数

• 因为在递归中，只有归才是产生答案的过程，所以可以从边界直接开始推出答案

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];
//     if(x>n) return 0;//     if(Spv>=vi[x]) //表示可以选
//     {
//         //选/不选
//         return mem[x][Spv]=max(dfs(x,Spv-vi[x])+wi[x],dfs(x+1,Spv));
//     }
//     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';for(int i=1;i<=n;i++)   //第几个物品{for(int j=0;j<=v;j++) //体积值{if(j>=vi[i])	表示可以选f[i][j]=max(f[i-1][j],f[i][j-vi[i]]+wi[i]); //不选/选else	//空间不够，不能拿当前物品f[i][j]=f[i-1][j];}}cout<<f[n][v];
}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、倒序遍历物品总是怪怪的，那么可不可以正序枚举呢，当然是可以的。

• 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,Spv-vi[x])+wi[x]);//     mem[x][Spv]=sum;
//     return sum;
// }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][j-vi[i]]+wi[i]); //不选/选}}cout<<f[n][v];
}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、看下图，如果是正序的话，那么结果就会从：i 的状态–> i-1的状态

• 也就是从已经拿过第i件商品的情况下，考虑在相同体积下是否要继续拿第i件商品

2、而物品$i$的状态此时表明已经考虑过了$i$这个物品，也就是已经选过了$i$

3、那么此时就变成了从这个物品已经选过的状态—>下一个状态，那么此时，就表明这个物品就重复选了！！！，这就变成了完全背包！！！

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];
//     if(x>n) return 0;//     if(Spv>=vi[x]) //表示可以选
//     {
//         //选/不选
//         return mem[x][Spv]=max(dfs(x,Spv-vi[x])+wi[x],dfs(x+1,Spv));
//     }
//     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';for(int i=1;i<=n;i++)   //第几个物品{for(int j=0;j<=v;j++) //体积值{if(j>=vi[i])  f[j]=max(f[j],f[j-vi[i]]+wi[i]); //不选/选}}cout<<f[v];
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _ =1; //cin >> _;while (_--) solve();system("pause");return 0;
}

总结：