Knapsack Cryptosystem

让你求用n个数中任意选择多个加和组成m，让你输出方案。

分析：首先可以想到的是暴力搜索但是2^36次方显然是不可以的，因而我们可以采用折半搜索，分两组爆搜答案，从而大大减少时间复杂度。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2621440;
ll a[maxn], b[maxn], n, m, cnt, flag;

struct nod{
    ll sum;
    string s = "";
} c[maxn];
void dfs1(int pos, int top, ll sum, string s)
{
    if(pos == top)
    {
        c[++cnt].sum = sum;
        c[cnt].s = s;
        return;
    }
    dfs1(pos + 1, top, sum + a[pos], s + "1");
    dfs1(pos + 1, top, sum, s + "0");
}

void dfs(int pos, int top, ll sum, string s)
{
    if(flag) return;
    if(pos == top)
    {
        int d = lower_bound(b + 1, b + cnt + 1, m - sum) - b;
        if(sum + b[d] == m)
        {
            cout << c[d].s << s << '\n';
            flag = 1;
        }
        return;
    }
    if(pos > top) return;
    dfs(pos + 1, top, sum + a[pos], s + "1");
    dfs(pos + 1, top, sum, s + "0");

}

bool cmp(nod a, nod b)
{
    return a.sum < b.sum;
}
int main()
{
    flag = 0;
    scanf("%lld%lld", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    dfs1(1, n / 2 + 1, 0, "");
    sort(c + 1, c + cnt + 1, cmp);
    for(int i = 1; i <= cnt; i++) b[i] = c[i].sum;
    dfs(n / 2 + 1, n + 1, 0, "");
    return 0;
}