01背包分支界限法C

以下是01背包问题的分支界限法C语言实现：

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

#define MAX_N 1000

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

typedef struct {
    int level;  // 当前扩展结点所在的层数
    int profit;  // 当前扩展结点的价值
    int weight;  // 当前扩展结点的重量
    int bound;  // 当前扩展结点的价值上界
} Node;

int n;  // 物品数量
int W;  // 背包容量
Item items[MAX_N];  // 物品数组
Node queue[MAX_N];  // 活结点队列
int front, rear;  // 队列的头尾指针

// 比较函数，用于qsort排序
int cmp(const void *a, const void *b) {
    Item *x = (Item *)a;
    Item *y = (Item *)b;
    double r1 = (double)x->v / x->w;
    double r2 = (double)y->v / y->w;
    if (r1 > r2) {
        return -1;
    } else if (r1 < r2) {
        return 1;
    } else {
        return 0;
    }
}

// 计算价值上界
int bound(Node u) {
    if (u.weight >= W) {
        return 0;
    }
    int j = u.level + 1;
    int bound = u.profit;
    int totweight = u.weight;
    while (j <= n && totweight + items[j].w <= W) {
        totweight += items[j].w;
        bound += items[j].v;
        j++;
    }
    if (j <= n) {
        bound += (W - totweight) * items[j].v / items[j].w;
    }
    return bound;
}

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

    // 初始化队列
    Node u, v;
    u.level = 0;
    u.profit = 0;
    u.weight = 0;
    u.bound = bound(u);
    front = rear = 0;
    queue[rear++] = u;

    // 迭代扩展结点
    int maxprofit = 0;
    while (front < rear) {
        u = queue[front++];
        if (u.bound > maxprofit) {
            // 扩展左儿子结点
            v.level = u.level + 1;
            v.weight = u.weight + items[v.level].w;
            v.profit = u.profit + items[v.level].v;
            if (v.weight <= W && v.profit > maxprofit) {
                maxprofit = v.profit;
            }
            v.bound = bound(v);
            if (v.bound > maxprofit) {
                queue[rear++] = v;
            }

            // 扩展右儿子结点
            v.weight = u.weight;
            v.profit = u.profit;
            v.bound = bound(v);
            if (v.bound > maxprofit) {
                queue[rear++] = v;
            }
        }
    }

    return maxprofit;
}

int main() {
    // 读入数据
    scanf("%d%d", &n, &W);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &items[i].v, &items[i].w);
    }

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

    // 输出结果
    printf("%d\n", maxprofit);

    return 0;
}