折半枚举的思想来源于双向搜索,主要解决的就是当问题规模较大时,无法枚举所有元素的组合,但能枚举一半元素的组合.
题目:POJ2785
题目大概意思就是给出ABCD四个数列,每个数列有n个整数.从四个数列各取出一个数,将他们相加.求和为0的组合个数.
如果直接暴力求解的话,时间复杂度是O(N4),是不可接受的.
但是如果折半来枚举,只要分别枚举每个A+B,和C+D,求能够使得(A+B)=-(C+D)的组合数就行了.这样子时间复杂度就降低到了O(N2).
#pragma GCC optimize("Ofast")
#include<algorithm>
#include<cstdio>
using namespace std;
#define MAXN 4005
typedef long long ll;
ll a[MAXN], b[MAXN], c[MAXN], d[MAXN];
ll CD[MAXN*MAXN];
int n;
int main()
{
scanf("%d", &n);
for(int i=0;i<n;++i)
{
scanf("%lld%lld%lld%lld", &a[i], &b[i], &c[i], &d[i]);
}
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
CD[i*n+j] = c[i]+d[j];
}
ll n2 = n*n;
sort(CD, CD+n2);
ll tmp;
ll ans=0;
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
{
tmp = -(a[i]+b[j]);
ans += upper_bound(CD, CD+n2, tmp) - lower_bound(CD, CD+n2, tmp);
}
}
printf("%lld\n", ans);
}
当背包问题的规模很大时,算法的时间复杂度是指数级增长的,那么将无法解决问题.
折半枚举就可以分别枚举数组的前半部分和后半部分.
首先,对w和v建立一个pair,然后按照字典序进行排序.接着,枚举前半部分,然后去除多余的组合(其实就是去除性价比很低的物品,也就是重量大,价值还低的)
然后枚举后半部分,并且在前半部分中搜索满足”前半重量比(最大重量-后半部分重量)小”的组合,然后求两部分价值相加的最大值.