分支限界法解决子集和数的问题

分支限界法是一种求解最优化问题的常用算法，它通过分解问题的解空间，逐步搜索可能的解，并根据约束条件和限界条件剪枝，以达到提高搜索效率和降低搜索复杂度的目的。

在子集和问题中，给定一个集合S和目标值T，需要从S中选出一些元素，使它们的和等于T。分支限界法可以通过以下步骤实现：

1. 定义结点：将选或者不选第i个元素作为结点，每个结点都有两个子结点，选或者不选第i+1个元素。

2. 定义扩展结点：对于每个结点，计算当前选定元素的和sum，如果sum已经大于T，则该结点不可扩展。否则，继续扩展其子结点。

3. 定义限界条件：对于每个结点，计算当前选定元素的和sum和剩余元素的和res，如果sum加上res小于T，则该结点不可扩展。否则，继续扩展其子结点。

4. 搜索过程：从根结点开始，依次扩展子结点，如果找到一个解，则更新最优解，并更新限界条件。如果搜索到叶子结点，返回上一层结点。

5. 剪枝：在搜索过程中，如果一个结点的限界条件不满足，则可以将其剪枝，即不再扩展其子结点。

下面是一个使用分支限界法解决子集和问题的示例程序：

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

const int MAXN = 100;

int n, T;
int a[MAXN], ans[MAXN], best[MAXN];

struct Node {
    int sum; // 当前选定元素的和
    int res; // 剩余元素的和
    int level; // 当前结点所在的层数
    vector<int> path; // 记录当前结点的路径
    Node(int s, int r, int l, vector<int>& p) : sum(s), res(r), level(l), path(p) {}
    bool operator<(const Node& other) const {
        return res > other.res; // 以剩余元素的和作为优先级
    }
};

void bfs() {
    priority_queue<Node> pq;
    vector<int> path;
    pq.push(Node(0, accumulate(a, a + n, 0), 0, path));
    while (!pq.empty()) {
        Node u = pq.top();
        pq.pop();
        if (u.sum > T) continue;
        if (u.level == n) {
            if (u.sum > best[0]) { // 更新最优解
                best[0] = u.sum;
                memcpy(ans, u.path.data(), n * sizeof(int));
            }
            continue;
        }
        if (u.res + u.sum <= best[0]) continue; // 剪枝
        vector<int> vpath = u.path;
        vpath.push_back(1);
        pq.push(Node(u.sum + a[u.level], u.res - a[u.level], u.level + 1, vpath));
        vpath.pop_back();
        vpath.push_back(0);
        pq.push(Node(u.sum, u.res - a[u.level], u.level + 1, vpath));
    }
}

int main() {
    cin >> n >> T;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n);
    reverse(a, a + n); // 从大到小排序，优先搜索大的数
    bfs();
    cout << "Subset sum: " << best[0] << endl;
    cout << "Subset: ";
    for (int i = 0; i < n; i++) {
        if (ans[i]) cout << a[i] << " ";
    }
    cout << endl;
    return 0;
}

在该程序中，我们使用了一个优先队列来实现分支限界法的搜索过程。每次从队列中取出剩余元素和最大的结点进行扩展，如果该结点的限界条件不满足，则剪枝。如果搜索到一个叶子结点，则更新最优解并返回上一层结点。最终，输出找到的最优解和对应的子集。