c语言分支限界解决01背包问题

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

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

#define MAX_N 1000

typedef struct {
    int w; // 物品重量
    int v; // 物品价值
} Item;

typedef struct {
    int id; // 节点编号
    int w; // 当前背包重量
    int v; // 当前背包价值
    int bound; // 当前节点的价值上界
} Node;

int n; // 物品数量
int c; // 背包容量
Item items[MAX_N]; // 物品数组
int bestv; // 最优解的价值
int bestx[MAX_N]; // 最优解的解向量

// 比较函数，用于qsort排序
int cmp(const void *a, const void *b) {
    Item *ia = (Item *)a;
    Item *ib = (Item *)b;
    double va = (double)ia->v / ia->w;
    double vb = (double)ib->v / ib->w;
    return vb > va ? 1 : vb < va ? -1 : 0;
}

// 计算节点的价值上界
int bound(Node *node) {
    if (node->w >= c) {
        return 0;
    }
    int bound = node->v;
    int j = node->id + 1;
    int w = node->w;
    while (j < n && w + items[j].w <= c) {
        w += items[j].w;
        bound += items[j].v;
        j++;
    }
    if (j < n) {
        bound += (c - w) * items[j].v / items[j].w;
    }
    return bound;
}

// 分支限界法求解01背包问题
void knapsack() {
    // 按单位重量价值从大到小排序
    qsort(items, n, sizeof(Item), cmp);

    // 初始化根节点
    Node root = { -1, 0, 0, 0 };
    Node *p = &root;

    // 初始化最优解
    for (int i = 0; i < n; i++) {
        bestx[i] = 0;
    }

    // 初始化堆
    MaxHeap heap;
    initMaxHeap(&heap);

    // 将根节点插入堆中
    insertMaxHeap(&heap, p);

    // 不断取出堆顶节点进行扩展，直到堆为空或者堆顶节点的价值上界小于等于当前最优解的价值
    while (!isEmptyMaxHeap(&heap)) {
        // 取出堆顶节点
        p = deleteMaxHeap(&heap);

        // 如果当前节点的价值上界小于等于当前最优解的价值，则剪枝
        if (p->bound <= bestv) {
            continue;
        }

        // 扩展左儿子节点
        Node left = { p->id + 1, p->w + items[p->id + 1].w, p->v + items[p->id + 1].v, 0 };
        left.bound = bound(&left);
        if (left.w <= c && left.v > bestv) {
            bestv = left.v;
            for (int i = 0; i <= left.id; i++) {
                bestx[i] = 0;
            }
            bestx[left.id] = 1;
        }
        if (left.bound > bestv) {
            insertMaxHeap(&heap, &left);
        }

        // 扩展右儿子节点
        Node right = { p->id + 1, p->w, p->v, 0 };
        right.bound = bound(&right);
        if (right.bound > bestv) {
            insertMaxHeap(&heap, &right);
        }
    }
}

int main() {
    // 读入物品数量和背包容量
    scanf("%d%d", &n, &c);

    // 读入物品重量和价值
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &items[i].w, &items[i].v);
    }

    // 求解01背包问题
    knapsack();

    // 输出最优解的价值和解向量
    printf("最优解的价值为：%d\n", bestv);
    printf("最优解的解向量为：");
    for (int i = 0; i < n; i++) {
        printf("%d ", bestx[i]);
    }
    printf("\n");

    return 0;
}