分支限界法 求印刷电路板的代码

由于分支限界法是一种求解最优解的算法，需要先确定问题的目标函数和约束条件，才能进行代码实现。以下是一个简单的求解印刷电路板最小成本的分支限界算法代码：

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

using namespace std;

const int MAXN = 15;
const int INF = 0x3f3f3f3f;

int n, m;
int cost[MAXN][MAXN];
int price[MAXN], limit[MAXN];
int ans = INF;

struct Node {
    int x[MAXN];
    int cnt;
    int sum;
    bool operator < (const Node &other) const {
        return sum > other.sum;
    }
};

void bfs() {
    priority_queue<Node> q;
    Node start;
    start.cnt = 0;
    start.sum = 0;
    for (int i = 1; i <= n; i++) {
        start.x[i] = 0;
    }
    q.push(start);
    while (!q.empty()) {
        Node cur = q.top();
        q.pop();
        if (cur.cnt == m) {
            ans = min(ans, cur.sum);
            continue;
        }
        for (int i = 1; i <= n; i++) {
            if (cur.x[i] + 1 <= limit[i]) {
                Node next = cur;
                next.x[i]++;
                next.cnt++;
                next.sum += cost[i][next.x[i]] + price[next.x[i]];
                q.push(next);
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> price[i] >> limit[i];
        for (int j = 1; j <= limit[i]; j++) {
            cin >> cost[i][j];
        }
    }
    bfs();
    cout << ans << endl;
    return 0;
}

该代码中，定义了一个Node结构体，用来表示每个状态，其中x[i]表示第i种元件已经选了几个，cnt表示已经选了多少种元件，sum表示当前的总花费。使用priority_queue实现了广度优先搜索，每次取出sum最小的状态进行扩展。在扩展时，枚举每种元件，如果该元件还可以选择，则将其添加到优先队列中。

该算法的时间复杂度为O(knlogk)，其中k为元件数量，n为每种元件可选数量的最大值。由于k和n都很小，因此该算法能够在较短的时间内求解出最优解。