折半搜索(meet in the middle)

发表于 | 更新于 | 分类于 ，

简单的思想,强大的能力,可惜可拓展范围不广

前置知识

大概木有吧,能学到这个东西大概你也会DFS了吧

进入正题

折半搜索,看起来很好玩的样子,我们用一道题来了解个大概

例题

题目描述

luogu-P4799 世界冰球锦标赛

今年的世界冰球锦标赛在捷克举行。Bobek 已经抵达布拉格，他不是任何团队的粉丝，也没有时间观念。他只是单纯的想去看几场比赛。如果他有足够的钱，他会去看所有的比赛。不幸的是，他的财产十分有限，他决定把所有财产都用来买门票。

给出 Bobek 的预算和每场比赛的票价，试求：如果总票价不超过预算，他有多少种观赛方案。如果存在以其中一种方案观看某场比赛而另一种方案不观看，则认为这两种方案不同。

题目简述

N场比赛,M元,每场价格不一定相同,求最多有多少种买的方案

分析例题

这是一道看起来十分简单的DFS题,但是,1560861893816!!!

再看一眼1560861920303

ou,shit!

$2^{40}$好像有点大啊

正式引入

折半搜索是一种针对方案计算而存在的算法,可以将时间复杂度开个根号

我们还是用例题来讲,

我们尝试将搜索的对象分为两部分,然后分别对其进行搜索,再分别记录结果

但是得到了这样的结果,我们并没有真正的结果啊,怎么办?

对于第一部分,我们定义一个方案$A$,第二部分定义一个方案$B$,满足$A+B<=M$,那么是不是第二部分任何小于$B$的方案都可以与$A$搭配?

那么我们将左右两部分得出的方案分别按花费排序,那就简单了,双指针直接秒杀.

再分析一波时间复杂度,$DFS:O(2^{n/2}),sort:O(2^{n/2} \cdot (n/2)),双指针: O(2^{n/2} \cdot (n/2))$

刚好$1e7$

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<bitset>
#include<vector>
#include<set>
#include<map>
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long db
#define si short int
#define bl bool
#define mem(a) memset(a,0,sizeof(a))
#define mee(a,b) memset(a,b,sizeof(a))
#define setnum(a,b,c) for(int kkk=1;i<=b;i++)a[kkk]=c[kkk];
#define setnums(a,b,c) for(int kkk=1;kkk<=b;kkk++)a[kkk]=c;
#define maxn 10000005
#define maxm
#define inf 0x7fffffff
#define r(a) a=read()
#define w(a) write(a);puts("")
#define W(a) write(a);printf(" ")
#define For(a,b,c) for(int a=b;a<=c;a++)
using namespace std;
ll Min(ll x,ll y){if(x<y)return x;return y;}
ll Max(ll x,ll y){if(x>y)return x;return y;}
ll read(){
	ll s=0,h=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')h=-1;c=getchar();}
	while(c>='0'&&c<='9'){s=s*10+c-'0';c=getchar();}
	return s*h;
}
void write(ll x){
	if(x>9){
		si tmp=x%10;
		write(x/10);
		putchar(tmp+'0');
	}
	else putchar(x+'0');
}
ll Pow(ll x,ll y,ll p){
	ll ans=1;
	while(y){
		if(y&1)ans=ans*x%p;
		x=x*x%p;y>>=1;
	}
	return ans;
}
ll n,m,v[maxn],a[maxn],b[maxn];
void Dfs(ll num,ll lim,ll val){
	if(num==lim+1){
		if(val>m)return;
		if(lim==n/2)a[++a[0]]=val;
		if(lim==n  )b[++b[0]]=val;
		return;
	}
	Dfs(num+1,lim,val);
	Dfs(num+1,lim,val+v[num]);
}
int main(){
	n=read();
	m=read();
	for(int i=1;i<=n;i++)
		v[i]=read();
	Dfs(1,n/2,0);
	Dfs(n/2+1,n,0);
	sort(a+1,a+a[0]+1);
	sort(b+1,b+b[0]+1);
	ll x=a[0],ans=0;
	for(int i=1;i<=b[0];i++){
		while(a[x]+b[i]>m)x--;
		ans+=x;
	}
	cout<<ans;
	return 0;
}

算法介绍

由上面这道题想必都可以对这个算法了解一些了吧,下面进行具体讲解

适用范围

这个算法适用于一些类似于N个物品由多种状态(如取与不取),由一定限制,问总共多少种方案.

上述时间复杂度大部分情况是$x^n$的时间(x是常数,也就是单一物品状态数)

思考方式

首先思考最为简单的暴力

然后通过将搜索范围折半分开的方式分别求出状态

但是其中会由一部分问题没有那么单纯,比如说给出的另外一道例题:luogu-P3067 平衡的奶牛群就会涉及到通过状态压缩来判重的手法.

最后对状态进行排序,并依次匹配

习题

luogu-P4799 世界冰球锦标赛

luogu-P3067 平衡的奶牛群