Knapsack Cryptosystem - 题解

标签与难度

标签: Meet-in-the-middle, 折半搜索, 子集和问题, 位运算, 哈希表, 搜索难度: 1900

题目大意喵~

各位小主人，下午好喵~ Amy酱遇到了一个关于密码学的问题，需要我们帮忙的说！

问题是这样的：给定一个包含 $n$ 个数字的数组 $\{a_i\}$ 和一个目标总和 $s$ 。我们需要从这个数组里找到一个子集，让这个子集里所有数字的和恰好等于 $s$ 。如果找到了，就要告诉 Amy酱我们选择了哪些数字。

简单来说，就是经典的 子集和问题 (Subset Sum Problem) 呐。

输入格式： 第一行是两个整数 $n$ 和 $s$ 。第二行是 $n$ 个整数，代表数组 $\{a_i\}$ 。

输出格式： 输出一个长度为 $n$ 的 01 字符串。如果第 $i$ 位是 '1'，表示我们选择了第 $i$ 个数；如果是 '0'，表示我们没有选择它。题目保证有解，所以我们只需要找到任意一个解就可以啦~

举个栗子：如果数组是 {10, 20, 30}，目标和是 30。我们可以选择第一个数和第二个数（ $10+20=30$ ），输出 "110"。也可以只选择第三个数（ $30=30$ ），输出 "001"。任何一个正确的组合都可以哦，喵！

解题思路分析

看到这个问题，我们最先想到的可能是... 暴力出奇迹！喵哈哈~ 我们可以尝试所有可能的子集。对于数组里的每个数，我们都有两种选择：选，或者不选。如果有 $n$ 个数，那么总共就有 $2^n$ 种组合。

如果 $n$ 很小，比如说 $n=20$ ，那么 $2^{20}$ 大约是 $10^6$ ，计算机跑起来毫无压力。但是，题目的 $n$ 最大可能到 40 左右。 $2^{40}$ 是一个天文数字（超过了 $10^{12}$ ），直接暴力搜索的话，就算是超级计算机也要跑到天荒地老，肯定会超时的说！

这时候，就需要我们聪明的猫猫头脑发挥作用啦！既然从一头跑到另一头太远了，我们为什么不从两头一起出发，在中间相遇呢？这就是 “折半搜索” (Meet-in-the-middle) 的思想，喵~

就像两只小猫从一条长长的隧道两端开始挖洞，最后在中间会合，这样每只小猫只需要挖一半的路程，效率就大大提高啦！

具体步骤是这样的：

分割数组：我们把 $n$ 个数分成两半。前一半有 mid = n / 2 个数，后一半有 n - mid 个数。
暴力搜索第一半：我们用暴力的方法，找出第一半所有可能的子集和。对于每个子集，我们都记录下它的和以及它是如何构成的（也就是那个01字符串）。因为第一半只有 mid (大约 $n/2 \approx 20$ ) 个数，所以组合数最多是 $2^{20}$ ，这是完全可以接受的。我们可以用一个 map 来存储这些信息：map<long long, string>，其中 key 是子集和，value 是对应的01选择串。
暴力搜索第二半并寻找配对：接下来，我们同样暴力搜索第二半的所有子集。对于第二半的每一个子集和 sum_B，我们想一想，要凑成目标 $s$ ，我们需要在第一半里找到一个子集和为 sum_A = s - sum_B 的组合。于是，我们就在第一步生成的 map 里查找是否存在 key 为 s - sum_B 的项。
合并答案：如果找到了！喵~ 这就意味着我们成功地从第一半找到了一个子集（和为 sum_A），又从第二半找到了一个子集（和为 sum_B），它们加起来正好是 $s$ ！我们只需要把它们各自的01选择串拼接起来，就是最终的答案啦！

这种方法的复杂度大概是 $O(2^{n/2} \cdot \log(2^{n/2}))$ ，当 $n=40$ 时，这大约是 $O(2^{20} \cdot 20)$ 的级别，完全可以在时限内完成。

那么如何高效地生成所有子集呢？我们可以用 位运算 (Bitmasking) 的技巧。一个整数的二进制表示天然地对应了一个集合的子集。例如，对于3个数，数字 5 的二进制是 101，就可以代表我们选择了第1个和第3个数。这样我们只需要从 0 遍历到 (1 << k) - 1 就可以枚举出 k 个元素的所有子集了，是不是很巧妙呀？

代码实现

下面就是我根据这个思路，精心重构的代码啦！注释写得很详细，希望能帮助小主人理解哦~

cpp

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <cmath>

// 使用 long long 来防止数字和过大导致溢出，喵~
using ll = long long;

int main() {
    // 加速输入输出，让程序跑得更快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    ll s;
    std::cin >> n >> s;

    std::vector<ll> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 1. 分割点，把数组分成两半
    int mid_point = n / 2;
    
    // 用 map 存储第一半所有子集的和以及对应的选择路径 (01串)
    std::map<ll, std::string> first_half_sums;

    // 2. 使用位运算 (bitmask) 遍历第一半的所有子集
    // (1 << mid_point) 就是 2 的 mid_point 次方，代表子集的总数
    for (int mask = 0; mask < (1 << mid_point); ++mask) {
        ll current_sum = 0;
        std::string current_path = "";
        for (int i = 0; i < mid_point; ++i) {
            // 检查 mask 的第 i 位是否为 1
            if ((mask >> i) & 1) {
                // 如果是 1，说明我们选择了 a[i]
                current_sum += a[i];
                current_path += '1';
            } else {
                // 如果是 0，说明没选
                current_path += '0';
            }
        }
        // 存储结果，如果和相同，后来的会覆盖先来的，不过没关系，我们只需要一个解
        first_half_sums[current_sum] = current_path;
    }

    // 3. 遍历第二半的所有子集，并寻找配对
    int remaining_len = n - mid_point;
    for (int mask = 0; mask < (1 << remaining_len); ++mask) {
        ll current_sum = 0;
        std::string current_path = "";
        for (int i = 0; i < remaining_len; ++i) {
            if ((mask >> i) & 1) {
                // a[mid_point + i] 是第二半的元素
                current_sum += a[mid_point + i];
                current_path += '1';
            } else {
                current_path += '0';
            }
        }

        // 计算需要在第一半中寻找的目标和
        ll needed_sum = s - current_sum;

        // 4. 在 map 中查找是否存在这个 needed_sum
        if (first_half_sums.count(needed_sum)) {
            // 找到了！喵~
            // 输出第一半的路径，再接上第二半的路径
            std::cout << first_half_sums[needed_sum] << current_path << std::endl;
            // 找到一个解就可以结束程序了
            return 0;
        }
    }

    return 0;
}

复杂度分析

时间复杂度: $O(2^{N/2} \cdot N)$ 我们把数组分成了两半，大小约为 $N/2$ 。第一部分，我们生成了 $2^{N/2}$ 个子集，每个子集的计算和 map 插入操作花费的时间与 $N/2$ 和 $\log(2^{N/2})$ 相关。总时间约为 $O(2^{N/2} \cdot (N/2 + \log(2^{N/2}))) = O(2^{N/2} \cdot N)$ 。第二部分，我们同样生成了 $2^{N/2}$ 个子集，对每个子集，我们在 map 中查找一次，花费时间约为 $\log(2^{N/2})$ 。总时间约为 $O(2^{N/2} \cdot (N/2 + \log(2^{N/2}))) = O(2^{N/2} \cdot N)$ 。所以，总的时间复杂度就是 $O(2^{N/2} \cdot N)$ 的说。
空间复杂度: $O(2^{N/2})$ 我们主要的额外空间开销是用于存储第一半子集和的 map。在最坏的情况下，第一半的 $2^{N/2}$ 个子集和都不同，所以 map 的大小会达到 $O(2^{N/2})$ 。

知识点总结

这道题真是一次愉快的思维探险呢，喵~ 我们来总结一下学到的东西吧！

子集和问题 (Subset Sum): 这是一个经典的 NP 完全问题。对于小规模数据，可以直接暴力搜索。但当数据规模变大时，就需要更巧妙的算法。
折半搜索 (Meet-in-the-middle): 这是解决指数级复杂度问题的强大武器！当问题的规模 $N$ 使得 $O(k^N)$ 无法接受，但 $O(k^{N/2})$ 可以接受时，就可以考虑将问题一分为二，分别求解再合并结果。它将复杂度从指数级大大降低。
位运算 (Bitmasking): 使用整数的二进制位来表示集合的子集是一种非常高效和简洁的编程技巧。for (int mask = 0; mask < (1 << n); ++mask) 是枚举 $n$ 个元素所有子集的标准写法，小主人们一定要掌握哦！
std::map 的使用: 在这个解法中，map 充当了哈希表的角色，帮助我们快速查找第一半中是否存在我们需要的那个“另一半”的和。它的 key 是和，value 是路径，完美地记录了我们需要的信息。

希望这篇题解能帮到你，喵~ 如果还有其他问题，随时可以再来找我玩哦！

Knapsack Cryptosystem - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​