c语言分支界限法的最佳调度问题

下面是使用 C 语言实现分支界限法的最佳调度问题的示例代码，其中使用了自己编写的优先队列：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_N 1000
#define MAX_K 100

struct State {
    int times[MAX_K];  // k 台机器的工作时间
    int depth;          // 搜索树的深度
    int cost;           // 当前状态完成全部任务的时间
};

struct PriorityQueue {
    State* data[MAX_N * MAX_K];
    int size;
};

void swap(State** a, State** b) {
    State* tmp = *a;
    *a = *b;
    *b = tmp;
}

void push(PriorityQueue* q, State* s) {
    int p = q->size;
    q->data[q->size++] = s;
    while (p > 0) {
        int parent = (p - 1) / 2;
        if (q->data[p]->cost < q->data[parent]->cost) {
            swap(&q->data[p], &q->data[parent]);
            p = parent;
        } else {
            break;
        }
    }
}

State* pop(PriorityQueue* q) {
    State* result = q->data[0];
    q->size--;
    q->data[0] = q->data[q->size];
    int p = 0;
    while (2 * p + 1 < q->size) {
        int left = 2 * p + 1;
        int right = 2 * p + 2;
        int child = left;
        if (right < q->size && q->data[right]->cost < q->data[left]->cost) {
            child = right;
        }
        if (q->data[child]->cost < q->data[p]->cost) {
            swap(&q->data[p], &q->data[child]);
            p = child;
        } else {
            break;
        }
    }
    return result;
}

int best_time;   // 最优解
int tasks[MAX_N];  // n 个任务需要完成的时间
int k;          // k 台机器可并行工作

void branch_bound() {
    PriorityQueue q = {{0}, 0}; // 优先队列
    State* s0 = (State*)malloc(sizeof(State));
    for (int i = 0; i < k; i++) {
        s0->times[i] = 0;
    }
    s0->depth = 0;
    s0->cost = 0;
    push(&q, s0); // 初始状态
    while (q.size > 0) {
        State* s = pop(&q);
        if (s->depth == sizeof(tasks) / sizeof(tasks[0])) {
            best_time = s->cost;
            break; // 已找到最优解
        }
        for (int i = 0; i < k; i++) {
            State* s2 = (State*)malloc(sizeof(State));
            *s2 = *s;
            s2->times[i] += tasks[s->depth]; // 将任务分配给机器 i
            s2->depth++;
            s2->cost = INT_MIN;
            for (int j = 0; j < k; j++) {
                if (s2->times[j] > s2->cost) {
                    s2->cost = s2->times[j];
                }
            }
            if (s2->cost < best_time) {
                push(&q, s2); // 只加入可行状态
            } else {
                free(s2);
            }
        }
        free(s);
    }
    while (q.size > 0) {
        free(pop(&q));
    }
}

int main() {
    int n;
    printf("请输入任务数量 n 和可并行工作的机器数量 k：");
    scanf("%d %d", &n, &k);
    printf("请输入每个任务需要完成的时间：");
    for (int i = 0; i < n; i++) {
        scanf("%d", &tasks[i]);
    }
    branch_bound();
    printf("最早完成时间为：%d\n", best_time);
    return 0;
}

注意在自己编写的优先队列中，使用了堆排序来维护队列。在实际应用中，可以根据具体的问题进行优化，例如使用剪枝策略来加速搜索。