折半枚举(双向搜索)

折半枚举的思想来源于双向搜索,主要解决的就是当问题规模较大时,无法枚举所有元素的组合,但能枚举一半元素的组合.

题目:POJ2785

题目大概意思就是给出ABCD四个数列,每个数列有n个整数.从四个数列各取出一个数,将他们相加.求和为0的组合个数.

如果直接暴力求解的话,时间复杂度是O(N⁴),是不可接受的.

但是如果折半来枚举,只要分别枚举每个A+B,和C+D,求能够使得(A+B)=-(C+D)的组合数就行了.这样子时间复杂度就降低到了O(N²).

AC代码

#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,然后按照字典序进行排序.接着,枚举前半部分,然后去除多余的组合(其实就是去除性价比很低的物品,也就是重量大,价值还低的)

然后枚举后半部分,并且在前半部分中搜索满足”前半重量比(最大重量-后半部分重量)小”的组合,然后求两部分价值相加的最大值.

转载请注明来源:https://www.longjin666.top/?p=1202

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~