（三）蛮力法

2023-11-19 21:20:40

蛮力法（brute force method，也称为穷举法或枚举法）是一种简单直接地解决问题的方法，常常直接基于问题的描述，所以，蛮力法也是最容易应用的方法。

蛮力法特性：

（1）理论上，蛮力法可以解决可计算领域的各种问题。

（2）蛮力法经常用来解决一些较小问规模的问题。

（3）对于一些重要的问题（如排序、查找、串匹配），蛮力法可以设计一些合理的算法，这些算法具有实用价值，而且不受输入规模的限制。

（4）蛮力法可以作为某类问题时间性能的下界，来衡量同样问题的其他算法是否具有更高的效率。

查找问题中使用蛮力法。

顺序查找：

是指在查找集合中一次查找值为k的元素，若查找成功，则给出元素在查找集合中的位置；若查找失败，则给出失败信息。

【想法】：将查找集合放在一维数组中，然后从数组的一端向另一端逐个将元素与带查找值进行比较，若相等，则查找成功，给出该元素在查找中的序号；若整个数组检测完仍未找到与带差值相等的元素，则查找失败，给出失败标志0。我们在查找过程中还要注意下标是否越界的问题。

算法的实现方法一：

int SeqSearch1(int r[] ,int n, int k) //数组r[1] r[n]中存放查找集合。

{

int i = n;

while(i>0 && r[i]!k) //注意检测比较位置是否越界。

{ i--; }

return i;

}

上述算法我们每次都要去判断数组的下标是否越界，为了避免在查找过程中每一次比较前都要判断查找位置是否越界，可以设置观察哨，即将待查值放在查找方向的“尽头”处，则比较位置i至多移动到下标0处。改进的顺序查找算法c的代码如下所示：

int SeqSearch(int r[] , int n, int k) //数组r[1] r[n]中存放查找集合。

{

int i = n; //从数组的高端开始查找。

r[0]=k; //数组第一个元素放置要查找的元素。

while(r[i] != k) //不用检测和比较位置是否越界。

{

i--;

}

return i;

}

蛮力法解决0/1背包问题。

【问题描述】：一个强盗去一个宝藏的山洞中取宝藏，但宝藏很多很多种，LV包，香奈儿钱包，劳力士刮胡刀，一颗超大的金珍珠等等，强盗带的仅仅有一个包，包中的容量就是那么大，能盛下的东西就那么多，每个珍宝都有自己的重量和价值，那强盗怎么装宝藏，让包中东西的价值最大，同时不超过包中的重量。你要是那个强盗怎么装入包中呢？这个强盗用蛮力法，就是在包中试装了各种宝藏，幸好，宝藏的品种没有超过十种。

【官方描述】：

给定n个重量为{w1，w2，w3，....，wn} ，价值为{v1，v2，v3，.....vn} 的物品和一个容量为C的背包，0/1 问题背包问题，求这些物品中的一个最有价值的子集，并且能够装入背包中。

【思路】：用蛮力法解决0/1背包问题，需要考虑n个给定物品的子集，找出所有重量不超过背包容量的子集，计算可能子集的总价值，然后找出价值最大的子集。

【例题】：

例如：给定4个重量为{7,3,4,5} ，价值为{42,12,40,25}，和一个容量为10的背包。

下表来描述蛮力法求解背包的过程。把四个包按照重量7 3 4 5 的顺序编号为1 2 3 4 。

【复杂度分析】：

采用蛮力法求解0/1背包问题的时间复杂度为：T(n)=O(2的n次方)

【C语言程序代码】：

#include<iostream>
#include<algorithm>
using namespace std;
#define N 100	//最多可能物体数
struct goods	//物品结构体
{
	int sign;	//物品序号
	int w;	//物品重量
	int p;	//物品价值
}a[N];
bool m(goods a,goods b)
{
	return (a.p/a.w)>(b.p/b.w);
}
int max(int a,int b)
{
	return a<b?b:a;
}
int n,C,bestP=0,cp=0,cw=0;
int X[N],cx[N];
/*蛮力法求解0/1背包问题*/
int Force(int i)
{
	if(i>n-1){
		if(bestP<cp&&cw+a[i].w<=C){
			for (int k=0;k<n;k++)	X[k]=cx[k];//存储最优路径
			bestP=cp;
		}
		return bestP;
	}
	cw=cw+a[i].w;
	cp=cp+a[i].p;
	cx[i]=1;	//装入背包
	Force(i+1);
	cw=cw-a[i].w;
	cp=cp-a[i].p;
	cx[i]=0;	//不装入背包
	Force(i+1);
	return bestP;
}
int KnapSack1(int n,goods a[],int C,int x[])
{
	Force(0);
	return bestP;
}