2023年8月1日发(作者：)

java蛮⼒法背包问题_[算法课]五种蛮⼒法解决01背包问题⽂章⽬录注明：题⽬要求只能使⽤蛮⼒法算法标签：全排列，枚举，⼆进制，dfs，数组题⽬简介思路AC代码⽅法⼀：字符串蛮⼒⽅法⼆：⼆进制枚举⽅法三：DFS三.２闫⽼板思考⾓度⽅法四：全排列⽅法五：数组蛮⼒答案注明：题⽬要求只能使⽤蛮⼒法算法标签：全排列，枚举，⼆进制，dfs，数组题⽬简介0/1背包问题【算法中⾮常经典的⼀个例题，多种不同的算法可以来实现】有n个重量分别是w1,w2…,wn的物品(物品编号为1-n)它们的价值分别为v1,v2,…,vn给定⼀个容量为W的背包。设计从这些物品中选取⼀部分放⼊该背包的⽅案。每个物品要么选中要么不选中【每种物品是唯⼀的】，要求选中的物品不仅能够放在背包中【能放得下】，⽽且具有最⼤的价值。并对如下所展⽰的5个物品求出W=10时的最佳解。物品编号 重量 价值1 2 62 2 33 6 54 5 45 4 6分析：并对如的5个物品求出W不超过10时的最佳解。思路我们设定有五个物品五个物品⼀开始都不选⽤string表⽰为 00000⽤j来控制状态选择1我们可以利⽤穷举写出5个变量的全排列⽽5个变量分别可以代表的当前状态下的当前位⼦的选择于是我们建⽴新的字符串，全排列的中的状态赋值即可，这样我们就得到了所有可能的选择状态。然后更新maxv和str即可2⽤⼆进制枚举形如1011表⽰选择，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 i=0;i<1<<5;i++)//⼆进制最⼤可能选择数{for(int j=0;j<5;j++)ww += (i>>j&1)*w[j], vv += (i>>j&1)*v[j];/判断当前位⼦是否被选择,更新0或1倍⽬标值的数值if (ww <= W && vv > maxv)maxv = vv,strres=i;//更新vv = 0, ww = 0;}for(int i=0;i<5;i++)cout<>i&1);//因为是选择情况，所以直接输出cout maxv){maxv = ans;return ;}for(int i=0;i<5;i++)if(!str[i]&&tw>=w[i]){str[i]=1;dfs(tw-w[i],ans+v[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 i=0;i<5;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)cout maxv)maxv = vv, str = s; //记录此时的s的组合vv = 0, ww = 0;} while (next_permutation((),()));}for(int i=0;i<5;i++)cout << str[i];cout maxv)maxv = vv;vv = 0, ww = 0;}cout << maxv << endl;getchar(); getchar();return 0;}答案1100115

2023年8月1日发(作者：)

java蛮⼒法背包问题_[算法课]五种蛮⼒法解决01背包问题⽂章⽬录注明：题⽬要求只能使⽤蛮⼒法算法标签：全排列，枚举，⼆进制，dfs，数组题⽬简介思路AC代码⽅法⼀：字符串蛮⼒⽅法⼆：⼆进制枚举⽅法三：DFS三.２闫⽼板思考⾓度⽅法四：全排列⽅法五：数组蛮⼒答案注明：题⽬要求只能使⽤蛮⼒法算法标签：全排列，枚举，⼆进制，dfs，数组题⽬简介0/1背包问题【算法中⾮常经典的⼀个例题，多种不同的算法可以来实现】有n个重量分别是w1,w2…,wn的物品(物品编号为1-n)它们的价值分别为v1,v2,…,vn给定⼀个容量为W的背包。设计从这些物品中选取⼀部分放⼊该背包的⽅案。每个物品要么选中要么不选中【每种物品是唯⼀的】，要求选中的物品不仅能够放在背包中【能放得下】，⽽且具有最⼤的价值。并对如下所展⽰的5个物品求出W=10时的最佳解。物品编号 重量 价值1 2 62 2 33 6 54 5 45 4 6分析：并对如的5个物品求出W不超过10时的最佳解。思路我们设定有五个物品五个物品⼀开始都不选⽤string表⽰为 00000⽤j来控制状态选择1我们可以利⽤穷举写出5个变量的全排列⽽5个变量分别可以代表的当前状态下的当前位⼦的选择于是我们建⽴新的字符串，全排列的中的状态赋值即可，这样我们就得到了所有可能的选择状态。然后更新maxv和str即可2⽤⼆进制枚举形如1011表⽰选择，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 i=0;i<1<<5;i++)//⼆进制最⼤可能选择数{for(int j=0;j<5;j++)ww += (i>>j&1)*w[j], vv += (i>>j&1)*v[j];/判断当前位⼦是否被选择,更新0或1倍⽬标值的数值if (ww <= W && vv > maxv)maxv = vv,strres=i;//更新vv = 0, ww = 0;}for(int i=0;i<5;i++)cout<>i&1);//因为是选择情况，所以直接输出cout maxv){maxv = ans;return ;}for(int i=0;i<5;i++)if(!str[i]&&tw>=w[i]){str[i]=1;dfs(tw-w[i],ans+v[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 i=0;i<5;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)cout maxv)maxv = vv, str = s; //记录此时的s的组合vv = 0, ww = 0;} while (next_permutation((),()));}for(int i=0;i<5;i++)cout << str[i];cout maxv)maxv = vv;vv = 0, ww = 0;}cout << maxv << endl;getchar(); getchar();return 0;}答案1100115