买瓜 参考代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 100;
int n, ans;
LL m;
LL num[maxn];
unordered_map<LL, int> cnt;
unordered_map<LL, int>::iterator it;

void dfs1(int depth, LL sum, int k) {
    if (sum > m) {
        return ;
    }
    if (depth == n / 2 + 1) {
        it = cnt.find(sum);
        if (it == cnt.end()) {
            cnt[sum] = k;
        } else {
            it->second = min(it->second, k);
        }
        return ;
    }
    dfs1(depth + 1, sum, k);
    dfs1(depth + 1, sum + num[depth], k);
    dfs1(depth + 1, sum + num[depth] / 2, k + 1);
}

void dfs2(int depth, LL sum, int k) {
    if (sum > m) {
        return ;
    }
    if (depth == n + 1) {
        it = cnt.find(m - sum);
        if (it != cnt.end()) {
            ans = min(ans, it->second + k);
        }
        return ;
    }
    dfs2(depth + 1, sum, k);
    dfs2(depth + 1, sum + num[depth], k);
    dfs2(depth + 1, sum + num[depth] / 2, k + 1);
}

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif // ExRoc
    ios::sync_with_stdio(false);

    cin >> n >> m;
    m <<= 1;
    for (int i = 1; i <= n; ++i) {
        cin >> num[i];
        num[i] <<= 1;
    }
    sort(num + 1, num + 1 + n);
    ans = INT_MAX;
    dfs1(1, 0, 0);
    dfs2(n / 2 + 1, 0, 0);
    cout << (ans == INT_MAX ? -1 : ans) << endl;

    return 0;
}