C语言分支限界算法详解（从零开始掌握0-1背包问题的高效解法）

应用场景：0-1背包问题

0-1背包问题是分支限界法的经典应用。问题描述如下：

• 给定 n 个物品，每个物品有重量 w[i] 和价值 v[i]
• 背包最大承重为 W
• 目标：选择物品使得总价值最大，且总重量不超过 W

C语言实现步骤

我们将使用优先队列（最大堆）来实现分支限界法，优先处理当前价值上界最高的节点。

1. 定义数据结构

// 节点结构体struct Node {    int level;      // 当前处理到第几个物品    int profit;     // 当前已获得的价值    int weight;     // 当前已使用的重量    float bound;    // 上界（用于剪枝）};// 物品结构体struct Item {    int weight;    int value;};

2. 计算上界函数（bound）

上界函数用于估算从当前节点出发可能达到的最大价值。若该上界小于当前已知最优解，则可剪枝。

float bound(struct Node u, int n, int W, struct Item items[]) {    if (u.weight >= W)        return 0;        float profit_bound = u.profit;    int j = u.level + 1;    int total_weight = u.weight;        // 贪心方式添加物品（允许部分物品，用于上界估计）    while (j < n && total_weight + items[j].weight <= W) {        total_weight += items[j].weight;        profit_bound += items[j].value;        j++;    }        // 添加最后一个物品的部分    if (j < n)        profit_bound += (W - total_weight) *                         ((float)items[j].value / items[j].weight);                            return profit_bound;}

3. 分支限界主函数

#include <stdio.h>#include <stdlib.h>// 比较函数（用于qsort，按单位价值降序）int cmp(const void *a, const void *b) {    struct Item *x = (struct Item *)a;    struct Item *y = (struct Item *)b;    double r1 = (double)x->value / x->weight;    double r2 = (double)y->value / y->weight;    return (r2 > r1) - (r2 < r1);}int knapsack(int W, struct Item items[], int n) {    qsort(items, n, sizeof(items[0]), cmp);        struct Node *queue = (struct Node *)malloc(n * sizeof(struct Node));    int front = 0, rear = 0;        struct Node u, v;    u.level = -1;    u.profit = u.weight = 0;    u.bound = bound(u, n, W, items);    queue[rear++] = u;        int maxProfit = 0;        while (front < rear) {        u = queue[front++];                if (u.level == -1)            v.level = 0;        else if (u.level != n - 1)            v.level = u.level + 1;        else            continue;                // 选择当前物品        v.weight = u.weight + items[v.level].weight;        v.profit = u.profit + items[v.level].value;                if (v.weight <= W && v.profit > maxProfit)            maxProfit = v.profit;                v.bound = bound(v, n, W, items);        if (v.bound > maxProfit)            queue[rear++] = v;                // 不选择当前物品        v.weight = u.weight;        v.profit = u.profit;        v.bound = bound(v, n, W, items);        if (v.bound > maxProfit)            queue[rear++] = v;    }        free(queue);    return maxProfit;}

4. 主函数测试

int main() {    int W = 50; // 背包容量    struct Item items[] = {{10, 60}, {20, 100}, {30, 120}};    int n = sizeof(items) / sizeof(items[0]);        printf("最大价值为: %d\n", knapsack(W, items, n));    return 0;}

为什么选择分支限界法？

相比暴力枚举（时间复杂度 O(2ⁿ)），分支限界法通过剪枝大幅减少搜索节点数量。尤其在0-1背包问题C语言实现中，合理设计上界函数可显著提升性能。

总结与算法优化技巧

通过本教程，你已掌握了C语言分支限界算法的基本原理与实现方法。记住以下几点可进一步提升代码效率：

• 对物品按单位价值排序，使上界估计更紧致
• 使用优先队列（堆）替代普通队列，优先探索高潜力分支
• 及时更新全局最优解，增强剪枝效果

现在，你已经具备了用C语言分支限界算法解决实际优化问题的能力！快去尝试修改代码，解决你自己的背包问题吧。