用分支限界法求解装载问题,用优先队列式求解c语言
时间: 2023-11-27 18:50:07 浏览: 72
装载问题是一种经典的NP完全问题,分支限界法是解决这类问题的常用方法之一。其基本思想是在搜索过程中,对每个搜索状态进行扩展,生成若干个子状态,然后从中选择一个最有希望的状态继续搜索。在装载问题中,搜索状态表示为已经装载的集装箱及其重量、当前未装载的集装箱及其重量、当前栈顶集装箱的重心位置和最优解等信息。
以下是C语言实现分支限界法求解装载问题的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <queue>
using namespace std;
#define MAXN 30
struct Node {
int w, u; // 已经装载的重量和下一个待装载的集装箱
double p; // 当前栈顶集装箱的重心位置
bool operator < (const Node& rhs) const {
return p < rhs.p; // 按照重心位置从小到大排序
}
};
int n, c, w[MAXN], v[MAXN], best; // 集装箱数量,容量,重量,体积,最优解
void dfs(int u, int cw, int cv, double cp) {
if (u == n) {
if (cw <= c && cv > best) best = cv; // 更新最优解
return;
}
if (cw + w[u] <= c) { // 尝试装入第u个集装箱
dfs(u + 1, cw + w[u], cv + v[u], (cp * cw + w[u] * (cp + 0.5)) / (cw + w[u])); // 更新重心位置
}
if (cv + (best - cv) / v[u] * v[u] > best) { // 估价函数剪枝
dfs(u + 1, cw, cv, cp);
}
}
void bfs() {
priority_queue<Node> q;
Node cur, nxt;
cur.w = cur.u = cur.p = 0;
q.push(cur);
while (!q.empty()) {
cur = q.top();
q.pop();
if (cur.u == n) {
if (cur.w <= c && cur.p > best) best = cur.p; // 更新最优解
return;
}
if (cur.w + w[cur.u] <= c) { // 尝试装入第u个集装箱
nxt.w = cur.w + w[cur.u];
nxt.u = cur.u + 1;
nxt.p = (cur.p * cur.w + w[cur.u] * (cur.p + 0.5)) / nxt.w; // 更新重心位置
if (nxt.p > best) q.push(nxt); // 重心位置优于当前最优解,加入队列
}
nxt.w = cur.w;
nxt.u = cur.u + 1;
nxt.p = cur.p;
if (cv + (best - cv) / v[cur.u] * v[cur.u] > best) q.push(nxt); // 估价函数剪枝
}
}
int main() {
scanf("%d%d", &n, &c);
for (int i = 0; i < n; i++) {
scanf("%d%d", &w[i], &v[i]);
}
bfs();
printf("%d\n", best);
return 0;
}
```
其中,dfs函数使用递归实现深度优先搜索,bfs函数使用优先队列实现广度优先搜索。在搜索过程中,使用估价函数剪枝来减少搜索空间。