分支界限法解决多机调用c++代码
时间: 2023-08-06 21:07:48 浏览: 31
以下是使用分支界限法解决多机调用问题的C++代码。其中,任务分配方式用一个数组job[]来表示,每个元素job[i]表示第i个任务分配给了哪个机器,如果job[i]=-1表示第i个任务还没有被分配。可用机器数用变量m表示,每个机器可用时间用数组time[]表示,time[i]表示第i个机器的可用时间。任务执行时间用二维数组cost[][]表示,cost[i][j]表示第i个任务在第j个机器上的执行时间。
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 20;
const int INF = 0x3f3f3f3f;
int n, m;
int time[MAXN], cost[MAXN][MAXN];
int job[MAXN], best_job[MAXN];
int min_cost = INF;
void dfs(int i, int cur_cost) {
if (i > n) {
if (cur_cost < min_cost) {
min_cost = cur_cost;
memcpy(best_job, job, sizeof(job));
}
return;
}
for (int j = 0; j < m; j++) {
if (time[j] >= cost[i][j]) {
time[j] -= cost[i][j];
job[i] = j;
dfs(i + 1, cur_cost + cost[i][j]);
time[j] += cost[i][j];
job[i] = -1;
}
}
}
void branch_bound() {
memset(job, -1, sizeof(job));
dfs(1, 0);
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < m; j++) {
cin >> cost[i][j];
}
}
for (int i = 0; i < m; i++) {
cin >> time[i];
}
branch_bound();
cout << "min_cost = " << min_cost << endl;
cout << "best job assignment: ";
for (int i = 1; i <= n; i++) {
cout << best_job[i] << " ";
}
cout << endl;
return 0;
}
```
在上述代码中,dfs()函数是核心部分,其中i表示当前任务编号,cur_cost表示当前的总花费。对于每个任务,枚举可用的机器,如果可行,则更新状态,继续搜索下一个任务。如果当前总花费已经大于等于当前最优解,就直接返回。最后输出最优解和最优任务分配方式。
注意:上述代码只是一个简单的示例,实际问题中还需要根据具体情况进行一些调整和优化。