使用c语言实现 分支界限法 01背包问题

好的，下面是使用C语言实现分支界限法解决01背包问题的代码：

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

#define MAX 100

int max(int a, int b) {
    return (a > b) ? a : b;
}

int knapsack(int n, int w[], int v[], int W) {
    int i, j, maxprofit = 0;
    int x[MAX], bestx[MAX];
    float bound, totalweight = 0;

    for (i = 1; i <= n; i++) {
        x[i] = 0;
        totalweight += w[i];
    }

    while (totalweight > W) {
        for (i = 1; i <= n; i++) {
            if (w[i] > totalweight - W) {
                x[i] = (totalweight - W) / w[i];
                totalweight = W;
                break;
            }
        }
    }

    struct node {
        int id;
        int profit;
        int weight;
        float bound;
    } u, v1, v2;

    u.id = 0;
    u.profit = 0;
    u.weight = 0;
    u.bound = 0;

    int q[MAX], front = -1, rear = -1;
    q[++rear] = 0;

    while (front != rear) {
        front++;
        u.id = q[front];

        if (u.id == 0) {
            v1.id = 1;
        } else if (u.weight + w[u.id] <= W) {
            v1.id = u.id + 1;
            v1.weight = u.weight + w[u.id];
            v1.profit = u.profit + v[u.id];
            v1.bound = u.bound - v[u.id] + (float)(W - v1.weight) * v[u.id + 1] / w[u.id + 1];
        } else {
            v1.id = u.id + 1;
            v1.weight = u.weight;
            v1.profit = u.profit;
            v1.bound = u.bound;
        }

        if (v1.bound > maxprofit) {
            q[++rear] = v1.id;
            if (v1.id == n + 1) {
                maxprofit = v1.profit;
                for (j = 1; j <= n; j++) {
                    bestx[j] = x[j];
                }
            }
        }

        if (u.bound > maxprofit) {
            v2.weight = u.weight;
            v2.profit = u.profit;
            v2.bound = u.bound - v[u.id + 1] + (float)(W - u.weight) * v[u.id + 1] / w[u.id + 1];
            v2.id = u.id + 1;

            if (v2.bound > maxprofit) {
                q[++rear] = v2.id;
            }
        }
    }

    printf("最优解为：%d\n", maxprofit);
    printf("最优解对应的x[]数组为：\n");

    for (i = 1; i <= n; i++) {
        printf("%d ", bestx[i]);
    }

    printf("\n");
    return maxprofit;
}

int main() {
    int n = 3;
    int w[4] = { 0, 10, 20, 30 };
    int v[4] = { 0, 60, 100, 120 };
    int W = 50;
    printf("背包容量为：%d\n", W);
    knapsack(n, w, v, W);
    return 0;
}

在这个代码中，我们定义了一个`node`结构体，用来存储每个节点的信息，包括节点编号、当前价值、当前重量以及当前的上界。我们使用一个队列来存储需要扩展的节点，每次取出队首元素进行扩展，直到队列为空。

在`knapsack`函数中，我们首先计算出每个物品的重量总和`totalweight`，如果`totalweight`大于背包容量`W`，则将部分物品的数量设置为最大值，使得它们的重量总和恰好等于`W`。然后我们初始化队列，将根节点加入队列中。在每次扩展节点时，我们分别计算选择当前物品和不选择当前物品两种情况下的上界，并将符合条件的节点加入队列中。

最后输出最优解和最优解对应的选择方案。在这个例子中，最优解为220，最优解对应的选择方案为选择第二个和第三个物品。