折半搜索+哈希 $O(2^{n/2})$

$首先每个瓜会被劈成两半，所以为了不出现0.5的情况\\ 现将每个瓜和目标瓜的重量乘2，这样每个瓜就有三种选择，\\ \begin{cases} 0 \rightarrow 不选这个瓜\\ 1 \rightarrow 选这个瓜，并将其劈成两半\\ 2 \rightarrow 选这一整个瓜 \end{cases}$

$这样直接用dfs爆搜的时间复杂度为O(3^n) = 10^{14}铁超时，\\ 采用折半搜索后的时间复杂度为O(3^{n / 2}) = 10^8\\ 由于dfs过程中有剪枝过程所以实际效率低于3^{n/2}$

#pragma GCC optimizer(2)
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef pair<int, int> PII;
typedef long long LL;

const int N = 31, M = 1e7 + 7;
const int null = 2e9 + 7;

int w[N];
int n, m;
int ans = 100;
PII h[M];

int find(int x){
    int key = x % M;
    while (h[key].first != x && h[key].first != null){
        key ++;
        if (key == M) key = 0;
    }
    return key;
}

void dfs_1(int u, int len, LL s, int cnt){
    if (s > m) return;
    if (u == len){
        int key = find(s);
        h[key] = {s, min(h[key].second, cnt)};
        return;
    }
    dfs_1(u + 1, len, s, cnt);
    dfs_1(u + 1, len, s + w[u], cnt);
    dfs_1(u + 1, len, s + w[u] / 2, cnt + 1);
}

void dfs_2(int u, int len, LL s, int cnt){
    if (s > m || cnt >= ans) return;
    if (u == len){
        int key = find(m - s);
        if (key != null)
            ans = min(ans, h[key].second + cnt);
        return;
    }

    dfs_2(u + 1, len, s, cnt);
    dfs_2(u + 1, len, s + w[u], cnt);
    dfs_2(u + 1, len, s + w[u] / 2, cnt + 1);
}

int main(){
    scanf("%d%d", &n, &m);
    m *= 2;

    for (int i = 0; i < n; i ++){
        scanf("%d", &w[i]), w[i] *= 2;
    }
    sort(w, w + n, greater<int>());

    for (int i = 1; i < M; i ++)
        h[i] = {null, null};

    dfs_1(0, n / 2 - 1, 0, 0);//折半也卡死，必须前移一项，粪数据:(
    dfs_2(n / 2 - 1, n, 0, 0);

    if (ans == 100) puts("-1");
    else printf("%d\n", ans);
    return 0;
}