双向DFS

Acwing 算法提高课 双向DFS

前置知识 : unique的使用

双向dfs的意义:

与双向bfs相同,不过本质上是一个空间换时间的操作

在本题目中我们的思路

• I. 将物品一分为二, 分为前$k$个和后$n-k$个
• II. 对前$k$个物品搜索得到一个可以组成的重量的集合A并排序去重($2^{k}$个物品)
• III.对后$n - k$个物品搜索, 每次得到一个重量即在A中寻找匹配最大总重量不超过w的最重物品,更新全局最优值

可以计算如此的时间复杂度 $2 ^ k + log_{2} 2 ^ {k} + 2 ^ {n - k} \times log_{2} 2 ^ {n - k}$
因为$n$最大取$46$
所以当k取$n / 2$(这里y总本来讲的是n/2+2但是n=1时可能死循环,所以n/2便可)时有近似最优时间复杂度

//2.11 15:53 Wa 7 / 13 (二分时忘记判是否越界了)
//2.11 16:01 AC

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 50, M = 1 << (N >> 1);
typedef long long LL;

int n, m, k, ans = 0;
int a[N], vis[M], cnt = 0;

void dfs1(int u, int s){

    if(u == k + 1){
        vis[++cnt] = s;
        return;
    }
    if((LL)s + a[u] <= m) dfs1(u + 1, s + a[u]);    
    dfs1(u + 1, s);
}

void dfs2(int u, int s){

    if(u == n + 1){
        
        int l = 1, r = cnt;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if((LL)s + vis[mid] <= m) l = mid;
            else r = mid - 1;
        }
        
        ans = max(ans, vis[l] + s);
        return;
    }
    if((LL)s + a[u] <= m) dfs2(u + 1, s + a[u]);    
    dfs2(u + 1, s);
}

int main(){
    scanf("%d%d", &m, &n);
    for(int i = 1; i <= n; i ++)
        scanf("%d", &a[i]);
    
    sort(a + 1, a + n + 1, greater<int>());
    
    k = n >> 1;
    
    dfs1(1, 0);
    
    sort(vis + 1, vis + cnt + 1);
    cnt = unique(vis + 1, vis + cnt + 1) - vis - 1;
    
    dfs2(k + 1, 0);
    
    cout << ans << endl;
    
    return 0;
}