Knapsack Cryptosystem

Posted on | In , , ,

题目链接

题意

有一个数列，现在要求你找出一个集合，使得数字之和为$s$。

思路

超大背包裸题。
记录自己超大背包签到失败的耻辱。
既然物品数量不多，那我们可以二进制枚举选择的物品，但是还是太慢啦。
我们换一种方式，可以折半枚举一部分物品，另一半我们去凑那个和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
const int N = 40;
map<ll, int> mp;
ll dp[1 << 20];
ll arr[N];
int main()
{
    int n;
    ll s;
    scanf("%d%lld", &n, &s);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &arr[i]);
    }
    if (n == 1)
    {
        if (s == 0)
            puts("0");
        else
            puts("1");
        return 0;
    }
    if (s == 0)
    {
        for (int i = 1; i <= n; i++)
            printf("0");
        putchar('\n');
        return 0;
    }
    int x = n / 2 + 1;
    int up = (1 << x);
    for (int i = 0; i < up; i++)
    {
        for (int j = 0; j < x; j++)
        {
            if (i & (1 << j))
                dp[i] += arr[j + 1];
        }
    }
    int upp = (1 << (n - x));
    for (int i = 0; i < upp; i++)
    {
        ll sum = 0;
        for (int j = 0; j < n - x; j++)
        {
            if (i & (1 << j))
                sum += arr[j + x + 1];
        }
        mp[sum] = i;
    }
    for (int i = 0; i < up; i++)
    {
        if (s < dp[i])
        {
            continue;
        }
        if (s == dp[i])
        {
            for (int j = 0; j < x; j++)
            {
                if (i & (1 << j))
                    putchar('1');
                else
                    putchar('0');
            }
            for (int j = x; j < n; j++)
                putchar('0');
            return 0;
        }
        if (mp.find(s - dp[i]) != mp.end())
        {
            int tmp = mp[s - dp[i]];
            for (int j = 0; j < x; j++)
            {
                if (i & (1 << j))
                    putchar('1');
                else
                    putchar('0');
            }
            for (int j = 0; j < n - x; j++)
            {
                if (tmp & (1 << j))
                    putchar('1');
                else
                    putchar('0');
            }
            putchar('\n');
            return 0;
        }
    }
    return 0;
}

0%