![java蛮力法背包问题_[算法课]五种蛮力法解决01背包问题](https://700zi.400zi.cn/uploadfile/img/14/874/22b067b812cfae388e14f397ea2b8d04.jpg)
文章目录
注明：题目要求只能使用蛮力法
算法标签：全排列，枚举，二进制，dfs，数组
题目简介
思路
AC代码
方法一：字符串蛮力
方法二：二进制枚举
方法三：DFS
三.２闫老板思考角度
方法四：全排列
方法五：数组蛮力
答案
注明：题目要求只能使用蛮力法
算法标签：全排列，枚举，二进制，dfs，数组
题目简介
0/1背包问题【算法中非常经典的一个例题，多种不同的算法可以来实现】
有n个重量分别是w1,w2…,wn的物品(物品编号为1-n)
它们的价值分别为v1,v2,…,vn
给定一个容量为W的背包。设计从这些物品中选取一部分放入该背包的方案。
每个物品要么选中要么不选中【每种物品是唯一的】，
要求选中的物品不仅能够放在背包中【能放得下】，而且具有最大的价值。
并对如下所展示的5个物品求出W=10时的最佳解。
物品编号 重量 价值
1 2 6
2 2 3
3 6 5
4 5 4
5 4 6
分析：并对如的5个物品求出W不超过10时的最佳解。
思路
我们设定有五个物品
五个物品一开始都不选
用string表示为 00000
用j来控制状态选择
1
我们可以利用穷举写出5个变量的全排列
而5个变量分别可以代表的当前状态下的当前位子的选择
于是我们建立新的字符串，全排列的中的状态赋值即可，这样我们就得到了所有可能的选择状态。
然后更新maxv和str即可
2
用二进制枚举
形如1000001
11110001
1表示选择，0表示未选择的方式
可参考我写的得到整数X
AC代码
方法一：字符串蛮力
#include
#include
#include
using 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;
}
方法二：二进制枚举
#include
using 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<
cout << maxv;
return 0;
}
方法三：DFS
无法保存最大路径
#include
using 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(tw<=W&&ans > 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;
}
三.２闫老板思考角度
#include
using 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<
cout<
cout << maxv;
return 0;
}
方法四：全排列
利用next_permuatation的特性，全排列，而我们只需要截取前面五位的状态即可
#include
#include
#include
using 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 i=0;i<5;i++)cout << str[i];
cout<
cout << maxv;
return 0;
}
方法五：数组蛮力
利用数组表示01
#include
#include
#include
using 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;
}
答案
11001
15
