做中介网站需要多少钱,动易网站官网,有没有做任务能兑换现金的网站,wordpress卡车主题一、暴力搜索#xff08;DFS#xff09; O ( n 2 ) O(n^2) O(n2)
1.1#xff09;思路解析
1、注意和01背包的区别在于每个物品可以无限次选择
注意在完全背包中#xff0c;当一个物品被选择过一次#xff0c;我们仍然需要考虑是否继续选择这个物品 01背包#xff1a; …
一、暴力搜索DFS O ( n 2 ) O(n^2) O(n2)
1.1思路解析
1、注意和01背包的区别在于每个物品可以无限次选择
注意在完全背包中当一个物品被选择过一次我们仍然需要考虑是否继续选择这个物品 01背包 max(dfs(x 1, Spv), dfs(x 1, Spv - vi[x]) wi[x])//不选/选完全背包max(dfs(x1,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(xn) return 0;if(Spvvi[x]) return dfs(x1,Spv); //物品体积太大选不了else return max(dfs(x1,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 resdfs(1,v);coutres\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)
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(xn) return 0;if(Spvvi[x]) //表示可以选{//选/不选return mem[x][Spv]max(dfs(x,Spv-vi[x])wi[x],dfs(x1,Spv));}else //空间不够不能拿当前物品{return mem[x][Spv]dfs(x1,Spv);}
}void solve()
{cin n v;for (int i 1; i n; i){cin vi[i]wi[i];}coutdfs(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(xn) return 0;// if(Spvvi[x]) //表示可以选
// {
// //选/不选
// return mem[x][Spv]max(dfs(x,Spv-vi[x])wi[x],dfs(x1,Spv));
// }
// else //空间不够不能拿当前物品
// {
// return mem[x][Spv]dfs(x1,Spv);
// }
// }void solve()
{cin n v;for (int i 1; i n; i){cin vi[i]wi[i];}//coutdfs(1,v)\n;for(int i1;in;i) //第几个物品{for(int j0;jv;j) //体积值{if(jvi[i]) 表示可以选f[i][j]max(f[i-1][j],f[i][j-vi[i]]wi[i]); //不选/选else //空间不够不能拿当前物品f[i][j]f[i-1][j];}}coutf[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 n-1 n−1开始递归此时边界刚刚好是为 1 1 1所以循环从 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 sum0;// if(xn) sum 0;
// else if(Spvvi[x]) sum dfs(x1,Spv); //物品体积太大选不了
// else sum max(dfs(x1,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 i1;in;i) //变为正序递推{for(int j0;jv;j){if(jvi[i]) f[i][j]f[i-1][j]; //选不了else f[i][j]max(f[i-1][j],f[i][j-vi[i]]wi[i]); //不选/选}}coutf[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的状态此时表明已经考虑过了 i i i这个物品也就是已经选过了 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(xn) return 0;// if(Spvvi[x]) //表示可以选
// {
// //选/不选
// return mem[x][Spv]max(dfs(x,Spv-vi[x])wi[x],dfs(x1,Spv));
// }
// else //空间不够不能拿当前物品
// {
// return mem[x][Spv]dfs(x1,Spv);
// }
// }void solve()
{cin n v;for (int i 1; i n; i){cin vi[i]wi[i];}//coutdfs(1,v)\n;for(int i1;in;i) //第几个物品{for(int j0;jv;j) //体积值{if(jvi[i]) f[j]max(f[j],f[j-vi[i]]wi[i]); //不选/选}}coutf[v];
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _ 1; //cin _;while (_--) solve();system(pause);return 0;
}总结
