实现分支限界0-1背包问题C语言代码

好的，以下是一个分支限界法解决0-1背包问题的C语言代码：

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

// 物品结构体
struct item {
    int value;   // 价值
    int weight;  // 重量
};

// 优先队列结构体
struct priority_queue {
    int size;           // 队列大小
    int capacity;       // 队列容量
    int *values;        // 储存价值的数组
    int *weights;       // 储存重量的数组
    int *bound_values;  // 储存上界的数组
};

// 初始化优先队列
struct priority_queue *init_priority_queue(int capacity) {
    struct priority_queue *pq = (struct priority_queue *)malloc(sizeof(struct priority_queue));
    pq->size = 0;
    pq->capacity = capacity;
    pq->values = (int *)malloc(capacity * sizeof(int));
    pq->weights = (int *)malloc(capacity * sizeof(int));
    pq->bound_values = (int *)malloc(capacity * sizeof(int));
    return pq;
}

// 销毁优先队列
void destroy_priority_queue(struct priority_queue *pq) {
    free(pq->values);
    free(pq->weights);
    free(pq->bound_values);
    free(pq);
}

// 向优先队列中插入元素
void insert(struct priority_queue *pq, int value, int weight, int bound_value) {
    if (pq->size < pq->capacity) {
        pq->values[pq->size] = value;
        pq->weights[pq->size] = weight;
        pq->bound_values[pq->size] = bound_value;
        pq->size++;
    }
}

// 交换两个元素
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 选择排序优先队列
void selection_sort(struct priority_queue *pq) {
    for (int i = 0; i < pq->size - 1; i++) {
        int min_index = i;
        for (int j = i + 1; j < pq->size; j++) {
            double unit_value1 = (double)pq->values[j] / pq->weights[j];
            double unit_value2 = (double)pq->values[min_index] / pq->weights[min_index];
            if (unit_value1 > unit_value2) {
                min_index = j;
            }
        }
        swap(&pq->values[i], &pq->values[min_index]);
        swap(&pq->weights[i], &pq->weights[min_index]);
        swap(&pq->bound_values[i], &pq->bound_values[min_index]);
    }
}

// 分支限界法求解0-1背包问题
int knapsack(struct item *items, int n, int capacity) {
    int max_value = 0;
    struct priority_queue *pq = init_priority_queue(n);
    int *current_values = (int *)calloc(n, sizeof(int));
    int *current_weights = (int *)calloc(n, sizeof(int));
    int *current_bound_values = (int *)calloc(n, sizeof(int));
    int current_weight = 0;
    int current_value = 0;
    int index = 0;
    int bound_value = 0;
    int temp_value = 0;
    int temp_weight = 0;
    int temp_bound_value = 0;
    int left_weight = 0;
    while (index != n) {
        if (current_weight + items[index].weight <= capacity) {
            current_weight += items[index].weight;
            current_value += items[index].value;
            current_values[index] = items[index].value;
            current_weights[index] = items[index].weight;
            index++;
            if (index == n) {
                max_value = current_value;
            }
        } else {
            bound_value = current_value;
            left_weight = capacity - current_weight;
            while (left_weight > 0 && index < n) {
                if (items[index].weight <= left_weight) {
                    bound_value += items[index].value;
                    left_weight -= items[index].weight;
                    current_values[index] = items[index].value;
                    current_weights[index] = items[index].weight;
                } else {
                    temp_value = items[index].value;
                    temp_weight = items[index].weight;
                    temp_bound_value = bound_value + (double)left_weight / temp_weight * temp_value;
                    insert(pq, current_value + temp_bound_value, current_weight + left_weight, temp_bound_value);
                    current_values[index] = (double)left_weight / temp_weight * temp_value;
                    current_weights[index] = left_weight;
                    bound_value += current_values[index];
                    left_weight = 0;
                }
                index++;
            }
            if (left_weight == 0) {
                max_value = current_value + bound_value;
            } else {
                break;
            }
        }
    }
    while (pq->size > 0) {
        selection_sort(pq);
        int value = pq->values[0];
        int weight = pq->weights[0];
        int bound_value = pq->bound_values[0];
        pq->size--;
        pq->values[0] = pq->values[pq->size];
        pq->weights[0] = pq->weights[pq->size];
        pq->bound_values[0] = pq->bound_values[pq->size];
        index = 0;
        while (index < n && current_weights[index] != 0) {
            index++;
        }
        if (index == n) {
            if (value > max_value) {
                max_value = value;
            }
            continue;
        }
        current_weight = weight;
        current_value = value - bound_value;
        current_values[index] = (double)current_weight / current_weights[index] * current_values[index];
        current_weights[index] = current_weight;
        bound_value = current_value;
        left_weight = capacity - current_weight;
        index++;
        while (left_weight > 0 && index < n) {
            if (items[index].weight <= left_weight) {
                bound_value += items[index].value;
                left_weight -= items[index].weight;
                current_values[index] = items[index].value;
                current_weights[index] = items[index].weight;
            } else {
                temp_value = items[index].value;
                temp_weight = items[index].weight;
                temp_bound_value = bound_value + (double)left_weight / temp_weight * temp_value;
                insert(pq, current_value + temp_bound_value, current_weight + left_weight, temp_bound_value);
                current_values[index] = (double)left_weight / temp_weight * temp_value;
                current_weights[index] = left_weight;
                bound_value += current_values[index];
                left_weight = 0;
            }
            index++;
        }
        if (left_weight == 0) {
            if (current_value + bound_value > max_value) {
                max_value = current_value + bound_value;
            }
        }
    }
    destroy_priority_queue(pq);
    free(current_values);
    free(current_weights);
    free(current_bound_values);
    return max_value;
}

int main() {
    int n = 5;  // 物品数量
    int capacity = 10;  // 背包容量
    struct item items[] = {{5, 3}, {4, 5}, {7, 2}, {8, 4}, {2, 1}};  // 物品数组
    int max_value = knapsack(items, n, capacity);  // 求解最大价值
    printf("The maximum value is %d.\n", max_value);
    return 0;
}

这段代码使用优先队列来存储可能的解，并使用选择排序来选择最优的解。由于每个节点只有两种可能的子节点，因此时间复杂度为 $O(2^n)$。此外，该算法还使用了一些剪枝技术，如上界估计和可行性剪枝，以提高效率。