网站建设一般都有什么项目,南昌建设工程质量监督网站,什么网站可以做问卷,产品网站建站文章目录注明#xff1a;题目要求只能使用蛮力法算法标签#xff1a;全排列#xff0c;枚举#xff0c;二进制#xff0c;dfs#xff0c;数组题目简介思路AC代码方法一#xff1a;字符串蛮力方法二#xff1a;二进制枚举方法三#xff1a;DFS三.#xff12;闫老板思考…文章目录注明题目要求只能使用蛮力法算法标签全排列枚举二进制dfs数组题目简介思路AC代码方法一字符串蛮力方法二二进制枚举方法三DFS三.闫老板思考角度方法四全排列方法五数组蛮力答案注明题目要求只能使用蛮力法算法标签全排列枚举二进制dfs数组题目简介0/1背包问题【算法中非常经典的一个例题多种不同的算法可以来实现】有n个重量分别是w1,w2…,wn的物品(物品编号为1-n)它们的价值分别为v1,v2,…,vn给定一个容量为W的背包。设计从这些物品中选取一部分放入该背包的方案。每个物品要么选中要么不选中【每种物品是唯一的】要求选中的物品不仅能够放在背包中【能放得下】而且具有最大的价值。并对如下所展示的5个物品求出W10时的最佳解。物品编号 重量 价值1 2 62 2 33 6 54 5 45 4 6分析并对如的5个物品求出W不超过10时的最佳解。思路我们设定有五个物品五个物品一开始都不选用string表示为 00000用j来控制状态选择1我们可以利用穷举写出5个变量的全排列而5个变量分别可以代表的当前状态下的当前位子的选择于是我们建立新的字符串全排列的中的状态赋值即可这样我们就得到了所有可能的选择状态。然后更新maxv和str即可2用二进制枚举形如1000001111100011表示选择0表示未选择的方式可参考我写的得到整数XAC代码方法一字符串蛮力#include#include#includeusing namespace std;int main(){int W 10, n 5;int w[5] { 2,2,6,5,4 }, v[5] { 6,3,5,4,6 };string pres 00000;int ww 0, vv 0, maxv 0;string str;char s[1000];for (int j 0; j 5; j)for (int a 0; a 5; a)for (int b 0; b 5; b)for (int c 0; c 5; c)for (int d 0; d 5; d)for (int e 0; e 5; e){if (a ! b a ! c a ! d a ! e);if (b ! c b ! d b ! e);if (c ! d c ! e);if (d ! e);pres[j]1;s[0] pres[a];s[1] pres[b];s[2] pres[c];s[3] pres[d];s[4] pres[e];//cout s[0] s[1] s[2] s[3] s[4] endl;for (int i 0; i 5; i)ww (s[i] - 0)*w[i], vv (s[i] - 0)*v[i];//当前背包重量不超过容量且vv当前背包价值大于最大价值if (ww W vv maxv)maxv vv, str s;//记录此时的s的组合vv 0, ww 0;}for (int i 0; i 5; i)cout str[i];cout endl;cout maxv endl;return 0;}方法二二进制枚举#includeusing namespace std;int ww,vv,maxv,strres;int main(){int W 10;int w[5] { 2,2,6,5,4 }, v[5] { 6,3,5,4,6 };for(int i0;i15;i)//二进制最大可能选择数{for(int j0;j5;j)ww (ij1)*w[j], vv (ij1)*v[j];/判断当前位子是否被选择,更新0或1倍目标值的数值if (ww W vv maxv)maxv vv,strresi;//更新vv 0, ww 0;}for(int i0;i5;i)couti1);//因为是选择情况所以直接输出coutcout maxv;return 0;}方法三DFS无法保存最大路径#includeusing namespace std;int ww,vv,maxv,strres;int W 10;int w[5] { 2,2,6,5,4 }, v[5] { 6,3,5,4,6 };int str[5];int ans[5];void dfs(int tw,int ans){if(twWans maxv){maxv ans;return ;}for(int i0;i5;i)if(!str[i]tww[i]){str[i]1;dfs(tw-w[i],ansv[i]);str[i]0;}}int main(){dfs(W,0);cout maxv;return 0;}三.闫老板思考角度#includeusing namespace std;int w[5] { 2,2,6,5,4 }, v[5] { 6,3,5,4,6 };int x[5];int maxv 0;int ans[5];void dfs(int i, int ww, int vv){if (i 5)if (ww 10 vv maxv) { maxv vv; for(int i0;i5;i)ans[i]x[i];return; }//记录最优状态else return;//这里给他加了个退出x[i] 1;dfs(i 1, ww w[i], vv v[i]);x[i]0;dfs(i 1, ww, vv);}int main(){dfs(0, 0, 0);for(auto x:ans)coutcoutcout maxv;return 0;}方法四全排列利用next_permuatation的特性全排列而我们只需要截取前面五位的状态即可#include#include#includeusing namespace std;int main(){int W 10, n 5;int w[5] {2, 2, 6, 5, 4}, v[5] {6, 3, 5, 4, 6};string s 0000011111;int ww 0, vv 0, maxv 0;string str;for (int j 0; j n; j){do{for (int i 0; i n; i)ww (s[i] - 0) * w[i], vv (s[i] - 0) * v[i];//当前背包重量不超过容量且vv当前背包价值大于最大价值if (ww W vv maxv)maxv vv, str s; //记录此时的s的组合vv 0, ww 0;} while (next_permutation(s.begin(),s.end()));}for(int i0;i5;i)cout str[i];coutcout maxv;return 0;}方法五数组蛮力利用数组表示01#include#include#includeusing namespace std;int s[5];int main(){int W 10, n 5;int w[5] { 2,2,6,5,4 }, v[5] { 6,3,5,4,6 };int ww 0, vv 0, maxv 0;string str;for (s[0]0; s[0] 2; s[0])for (s[1]0; s[1] 2; s[1])for (s[2]0; s[2] 2; s[2])for (s[3]0; s[3] 2; s[3])for (s[4]0; s[4] 2; s[4]){for (int i 0; i 5; i)ww (s[i])*w[i], vv (s[i])*v[i];if (ww W vv maxv)maxv vv;vv 0, ww 0;}cout maxv endl;getchar(); getchar();return 0;}答案1100115
