0-1背包问题分支界限法c可运行代码实现

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

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

#define MAX_N 1000  // 最大物品数量
#define MAX_W 1000  // 最大背包容量

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

typedef struct {
    int total_v;  // 当前已选择的物品总价值
    int total_w;  // 当前已选择的物品总重量
    int bound;  // 当前节点的价值上界
    int level;  // 当前节点所在的层数
    int taken[MAX_N];  // 当前已选择的物品列表
} Node;

int n;  // 物品数量
int W;  // 背包容量
Item items[MAX_N];  // 物品列表
Node nodes[MAX_N];  // 节点列表
int max_v = 0;  // 最优解的价值

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

// 计算节点的价值上界
int calc_bound(Node node) {
    int v = node.total_v;
    int w = node.total_w;
    int i;
    for (i = node.level; i < n; i++) {
        if (w + items[i].w <= W) {
            v += items[i].v;
            w += items[i].w;
        } else {
            v += (W - w) * items[i].r;
            break;
        }
    }
    return v;
}

// 分支界限法求解0-1背包问题
void knapsack() {
    int i, j;  // 循环变量
    int level = 0;  // 当前节点所在的层数
    int total_v = 0;  // 当前已选择的物品总价值
    int total_w = 0;  // 当前已选择的物品总重量
    int bound = 0;  // 当前节点的价值上界
    int taken[MAX_N] = {0};  // 当前已选择的物品列表
    Node root = {total_v, total_w, bound, level, {0}};  // 根节点

    // 计算每个物品的单位重量价值
    for (i = 0; i < n; i++) {
        items[i].r = (double)items[i].v / items[i].w;
    }

    // 将物品按照单位重量价值从大到小排序
    qsort(items, n, sizeof(Item), cmp);

    // 将根节点加入到待处理的节点列表
    nodes[0] = root;
    int num_nodes = 1;

    while (num_nodes > 0) {
        // 选择一个最有前途的节点进行分支
        Node node = nodes[--num_nodes];

        // 如果当前节点的价值上界小于当前最优解的价值，则剪枝
        if (node.bound < max_v) {
            continue;
        }

        // 如果当前节点已经是叶子节点，则更新最优解
        if (node.level == n) {
            max_v = node.total_v;
            continue;
        }

        // 选择该物品的子节点
        Node taken_node = node;
        taken_node.taken[node.level] = 1;
        taken_node.total_v += items[node.level].v;
        taken_node.total_w += items[node.level].w;
        taken_node.bound = calc_bound(taken_node);
        taken_node.level = node.level + 1;

        // 如果该子节点的价值上界大于当前最优解的价值，则将其加入到待处理的节点列表中
        if (taken_node.bound > max_v && taken_node.total_w <= W) {
            nodes[num_nodes++] = taken_node;
        }

        // 不选择该物品的子节点
        Node not_taken_node = node;
        not_taken_node.taken[node.level] = 0;
        not_taken_node.bound = calc_bound(not_taken_node);
        not_taken_node.level = node.level + 1;

        // 如果该子节点的价值上界大于当前最优解的价值，则将其加入到待处理的节点列表中
        if (not_taken_node.bound > max_v) {
            nodes[num_nodes++] = not_taken_node;
        }
    }
}

int main() {
    int i;

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

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

    // 求解0-1背包问题
    knapsack();

    // 输出最优解
    printf("%d\n", max_v);

    return 0;
}

在运行时，需要依次输入物品数量、背包容量以及每个物品的价值和重量。程序将输出最优解的价值。