分支限界法0-1背包问题c语言

下面是使用分支限界法解决0-1背包问题的C语言代码示例：

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

#define MAXN 100    // 最大物品数量
#define MAXW 1000   // 最大背包重量

typedef struct node {
    int profit;     // 当前节点的收益
    int weight;     // 当前节点的重量
    int level;      // 当前节点的层数
    float bound;    // 当前节点的上界
} Node;

int n, W;           // 物品数量，背包容量
int p[MAXN];        // 物品的收益
int w[MAXN];        // 物品的重量

Node queue[MAXN];   // 队列
int head, tail;     // 队头指针和队尾指针

// 比较函数：按照上界从大到小排序
int cmp(const void *a, const void *b) {
    return ((Node*)b)->bound - ((Node*)a)->bound;
}

// 计算当前节点的上界
float bound(int level, int weight, int profit) {
    if (weight >= W) {
        return profit;
    }
    float b = profit;
    int i = level + 1;
    int w = weight;
    while (i <= n && w + ::w[i] <= W) {
        b += p[i];
        w += ::w[i];
        i++;
    }
    if (i <= n) {
        b += (W - w) * 1.0 * p[i] / ::w[i];
    }
    return b;
}

// 添加一个节点到队列
void add(Node node) {
    queue[tail++] = node;
}

// 取出队头节点
Node pop() {
    return queue[head++];
}

// 分支限界法求解0-1背包问题
int knapsack() {
    Node node, left, right;
    node.level = 0;
    node.profit = 0;
    node.weight = 0;
    node.bound = bound(0, 0, 0);
    add(node);
    int max_profit = 0;
    while (head < tail) {
        node = pop();
        if (node.bound <= max_profit) {
            break;
        }
        if (node.level == n) {
            max_profit = node.profit;
            continue;
        }
        left.level = node.level + 1;
        left.weight = node.weight + w[left.level];
        left.profit = node.profit + p[left.level];
        left.bound = bound(left.level, left.weight, left.profit);
        if (left.bound > max_profit) {
            add(left);
        }
        right.level = node.level + 1;
        right.weight = node.weight;
        right.profit = node.profit;
        right.bound = bound(right.level, right.weight, right.profit);
        if (right.bound > max_profit) {
            add(right);
        }
        qsort(queue + head, tail - head, sizeof(Node), cmp);
    }
    return max_profit;
}

int main() {
    printf("请输入物品数量和背包容量：");
    scanf("%d%d", &n, &W);
    printf("请依次输入每个物品的收益和重量：\n");
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &p[i], &w[i]);
    }
    int max_profit = knapsack();
    printf("最大收益为：%d\n", max_profit);
    return 0;
}

该代码首先定义了一个节点结构体 `Node`，包含当前节点的收益、重量、层数和上界。然后定义了一个队列 `queue` 和队头指针和队尾指针 `head` 和 `tail`，用于存储待扩展的节点。

在 `cmp` 函数中，我们按照上界从大到小排序，这样每次从队列中取出的节点都是上界最大的节点，可以得到最优解。

在 `bound` 函数中，我们计算当前节点的上界，具体方法是先尽可能地装满背包，然后将剩余的空间用当前层下一个物品的单位收益来补充。

在 `knapsack` 函数中，我们首先将根节点加入队列中，然后不停地从队列中取出节点进行扩展，直到队列为空或者当前节点的上界小于等于当前的最优解。如果当前节点是一个叶子节点，则更新最优解。否则，分别创建左子树和右子树，计算它们的上界，并将它们加入队列中。最后，对队列中的节点按照上界从大到小排序，以便下一次取出上界最大的节点进行扩展。

最后，在 `main` 函数中，我们读入物品数量和背包容量，以及每个物品的收益和重量，然后调用 `knapsack` 函数求解最大收益，并输出结果。