用C语言实现分支限界法求0-1背包问题

以下是用C语言实现分支限界法求解0-1背包问题的代码：

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

#define MAX_N 100  // 最大物品数量
#define MAX_W 1000 // 最大背包容量

typedef struct Node {
    int level;          // 当前搜索的层数
    int profit;         // 当前已经获得的总价值
    int weight;         // 当前已经使用的总重量
    int bound;          // 当前状态的价值上界
    int selected[MAX_N]; // 当前已经选中的物品
} Node;

int n;               // 物品数量
int c;               // 背包容量
int w[MAX_N];        // 每个物品的重量
int p[MAX_N];        // 每个物品的价值
int max_profit = 0;  // 最大价值
int best_selected[MAX_N]; // 最优解选中的物品

void init() {
    // 初始化物品信息
    printf("请输入物品数量和背包容量：\n");
    scanf("%d%d", &n, &c);
    printf("请输入每个物品的重量和价值：\n");
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &w[i], &p[i]);
    }
}

int bound(Node *node) {
    // 计算当前状态的价值上界
    int profit_bound = node->profit;
    int weight_bound = node->weight;
    int i = node->level;
    while (i < n && weight_bound + w[i] <= c) {
        weight_bound += w[i];
        profit_bound += p[i];
        i++;
    }
    if (i < n) {
        profit_bound += (c - weight_bound) * p[i] / w[i];
    }
    return profit_bound;
}

void branch_and_bound() {
    // 初始化根节点
    Node root_node = {0, 0, 0, bound(&root_node), {0}};
    Node *cur_node = &root_node;

    // 初始化优先队列
    Node *queue[MAX_N] = {NULL};
    int front = 0, rear = 0;
    queue[rear++] = cur_node;

    // 不断扩展状态直到队列为空
    while (front < rear) {
        // 选择价值上界最大的节点进行扩展
        cur_node = queue[front++];
        if (cur_node->bound > max_profit) {
            // 扩展左儿子，即选择当前物品
            Node *left_node = (Node*)malloc(sizeof(Node));
            left_node->level = cur_node->level + 1;
            left_node->profit = cur_node->profit + p[left_node->level - 1];
            left_node->weight = cur_node->weight + w[left_node->level - 1];
            for (int i = 0; i < cur_node->level; i++) {
                left_node->selected[i] = cur_node->selected[i];
            }
            left_node->selected[left_node->level - 1] = 1;
            left_node->bound = bound(left_node);
            if (left_node->weight <= c && left_node->profit > max_profit) {
                max_profit = left_node->profit;
                for (int i = 0; i < n; i++) {
                    best_selected[i] = left_node->selected[i];
                }
            }
            if (left_node->bound > max_profit) {
                queue[rear++] = left_node;
            } else {
                free(left_node);
            }

            // 扩展右儿子，即不选择当前物品
            Node *right_node = (Node*)malloc(sizeof(Node));
            right_node->level = cur_node->level + 1;
            right_node->profit = cur_node->profit;
            right_node->weight = cur_node->weight;
            for (int i = 0; i < cur_node->level; i++) {
                right_node->selected[i] = cur_node->selected[i];
            }
            right_node->selected[right_node->level - 1] = 0;
            right_node->bound = bound(right_node);
            if (right_node->bound > max_profit) {
                queue[rear++] = right_node;
            } else {
                free(right_node);
            }
        } else {
            free(cur_node);
        }
    }
}

void print_result() {
    printf("最大价值为：%d\n", max_profit);
    printf("选中的物品编号为：");
    for (int i = 0; i < n; i++) {
        if (best_selected[i]) {
            printf("%d ", i + 1);
        }
    }
    printf("\n");
}

int main() {
    init();
    branch_and_bound();
    print_result();
    return 0;
}

在实现中，我们使用一个结构体 `Node` 来表示搜索状态，并维护了当前已经选中的物品信息。求解过程中，我们使用一个优先队列来维护状态集合，每次选择价值上界最大的节点进行扩展。扩展过程中，需要分别考虑选择当前物品和不选择当前物品两种情况，然后计算扩展后的状态的价值上界，并根据剪枝策略决定是否将该状态加入队列中进行进一步扩展。最终，队列为空时得到的最大价值即为最优解。