meet in the middle 复习笔记

前言

若干年前看过现在又忘了。这么简单都忘

所以今天来重新复习一下。

正题

考虑这样的问题：

给定 \(n\) 个物品的价格，你有 \(m\) 块钱，每件物品限买一次，求买东西的方案数。

\(n\leq 40\)，\(m\leq 10^{18}\)。

在看到数据范围之前，所有人的想法都是直接背包，看到数据范围后就寄了。

看样子不可用背包，那就用搜索吧。

直观的，我们考虑 \(O(2^n\times n)\) 的做法。

用 \(O(2^n)\) 的复杂度枚举每个物品是否购买，再 \(O(n)\) 复杂度判断是否合法。

但是看懂 \(n \leq 40\) 时就又寄了。

这是我们考虑 meet in the middle ，把时间复杂度变成 \(O(2^{\frac{n}{2}}+合并复杂度)\) 。

我们直接把当前的物品分成 \(1\sim \frac{n}{2}\) 和 \(\frac{n}{2}+1 \sim n\) 两个部分。

对于每一个部分我们都进行搜索，并把当前方案的花费 分两个数组 记录下来。

不难发现，到这为止，时间复杂度是 \(O(n^{\frac{n}{2}})\) 带有 \(2\) 的常数。

考虑怎么处理计算出来的各种方案的花费。

先考虑其中一个数组中的一种花费必选，然后直接二分查找即可。

（当然，之前要对这两个数组进行排序）

Code

笔者远古代码，没有人肉格式化，不喜勿喷。

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

using namespace std;

#define ll long long

#define re register

#define N 50

#define M 2000005

int max(ll a,ll b){return a>b?a:b;}

int min(ll a,ll b){return a<b?a:b;}

int n,num,visit[N];

ll m,a[N],num1[M],num2[M];

ll b[N],c[N],ans=0;

inline ll read(){

  ll s=0,t=1;

  char c=getchar();

  while((c<'0'||c>'9')&&c!='-')c=getchar();

  if(c=='-')c=getchar(),t=-1;

  while(c>='0'&&c<='9')s=(s<<1)+(s<<3)+(c^48),c=getchar();

  return s*t;

}

void dfs_b(int k){

  if(k>b[0]){

    ll s=0;

    for(int i=1;i<=b[0];i++)

    if(visit[i]==1)s+=b[i];

    num1[++num1[0]]=s;

    return;

  }

  visit[k]=1;

  dfs_b(k+1);

  visit[k]=0;

  dfs_b(k+1);

}

void dfs_c(int k){

  if(k>c[0]){

    ll s=0;

    for(int i=1;i<=c[0];i++)

    if(visit[i]==1)s+=c[i];

    num2[++num2[0]]=s;

    return;

  }

  visit[k]=1;

  dfs_c(k+1);

  visit[k]=0;

  dfs_c(k+1);

}

ll find(ll need){

  ll l=1,r=num2[0];

  ll mid,maxn=0;

  while(l<=r){

    mid=(l+r)/2;

    if(num2[mid]<=need){

      maxn=max(maxn,mid);

      l=mid+1;

    }

    else r=mid-1;

  }

  return maxn;

}

int main(void){

  scanf("%d",&n);

  m=read();

  for(int i=1;i<=n;i++)

  a[i]=read();

  num=n/2;

  for(int i=1;i<=num;i++)

  b[++b[0]]=a[i];

  for(int i=num+1;i<=n;i++)

  c[++c[0]]=a[i];

  memset(visit,0,sizeof(visit));

  dfs_b(1);

  memset(visit,0,sizeof(visit));

  dfs_c(1);

  sort(num2+1,num2+1+num2[0]);

  for(int i=1;i<=num1[0];i++){

    ll now=m-num1[i];

    if(now<0ll)continue;

    ans+=find(now);

  }

  printf("%lld\n",ans);

}

巴特西

meet in the middle 复习笔记

前言

正题

Code

最新文章

热门文章