装载问题分支限界法用C语言实现代码

装载问题是一个经典的组合优化问题，分支限界法是其中一种常见的求解方法。下面是使用C语言实现装载问题分支限界法的代码：

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

#define MAX_N 1000 // 最大物品数量
#define MAX_C 1000 // 最大容量

// 物品结构体
struct Item {
    int weight; // 重量
    int profit; // 价值
};

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

// 全局变量
int n, c; // 物品数量和背包容量
int max_profit; // 最优解
int max_weight; // 最优解对应的重量
struct Item items[MAX_N]; // 所有物品

// 比较函数，用于qsort排序
int cmp(const void *a, const void *b) {
    double r1 = ((struct Item *)a)->profit / (double)((struct Item *)a)->weight;
    double r2 = ((struct Item *)b)->profit / (double)((struct Item *)b)->weight;
    return (r2 - r1) > 0 ? 1 : -1;
}

// 计算当前节点的上界
int bound(struct Node node) {
    int remaining_weight = c - node.weight; // 剩余容量
    int bound = node.profit; // 上界初始化为当前价值
    int i = node.level;
    while (i < n && remaining_weight > 0) { // 遍历所有剩余的物品，直到装满背包或者没有物品了
        if (remaining_weight >= items[i].weight) { // 如果当前物品能够全部装入背包
            bound += items[i].profit; // 加上当前物品的价值
            remaining_weight -= items[i].weight; // 减去当前物品的重量
        } else { // 如果当前物品只能装一部分
            bound += (remaining_weight / (double)items[i].weight) * items[i].profit; // 加上部分价值
            remaining_weight = 0; // 背包已经装满，跳出循环
        }
        i++;
    }
    return bound;
}

// 装载问题分支限界法
void branch_and_bound() {
    // 初始化根节点
    struct Node root = { -1, 0, 0, 0 };
    root.bound = bound(root);

    // 使用堆栈保存所有未扩展的节点
    struct Node stack[MAX_N * 2];
    int top = 0;
    stack[top++] = root;

    while (top > 0) {
        // 取出当前最优的节点进行扩展
        struct Node node = stack[--top];

        // 如果当前节点的上界小于等于最优解，或者当前节点已经扩展完毕，则跳过
        if (node.bound > max_profit && node.level < n - 1) {
            // 扩展左节点（不装当前物品）
            struct Node left = { node.level + 1, node.profit, node.weight, 0 };
            left.bound = bound(left);
            stack[top++] = left;

            // 扩展右节点（装当前物品）
            struct Node right = { node.level + 1, node.profit + items[node.level + 1].profit, node.weight + items[node.level + 1].weight, 0 };
            right.bound = bound(right);
            if (right.weight <= c && right.profit > max_profit) { // 如果右节点符合条件，则更新最优解
                max_profit = right.profit;
                max_weight = right.weight;
            }
            if (right.bound > max_profit) { // 如果右节点的上界大于最优解，则加入堆栈
                stack[top++] = right;
            }
        }
    }
}

int main() {
    // 读入输入
    scanf("%d%d", &n, &c);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &items[i].weight, &items[i].profit);
    }

    // 按单位重量价值排序
    qsort(items, n, sizeof(struct Item), cmp);

    // 使用分支限界法求解
    branch_and_bound();

    // 输出结果
    printf("Max profit: %d\n", max_profit);
    printf("Max weight: %d\n", max_weight);

    return 0;
}

主要思路是使用一个堆栈保存所有未扩展的节点，每次取出堆栈中的最优节点进行扩展，直到堆栈为空。在扩展节点时，先计算当前节点的上界，如果上界小于等于当前最优解，则跳过该节点；否则，分别扩展左节点（不装当前物品）和右节点（装当前物品），并分别计算它们的上界。如果右节点符合条件，则更新最优解；如果右节点的上界大于当前最优解，则将其加入堆栈中。