分支限界法求解0-1背包问题,规定物品数量为10，背包容量为50，输入为20个数，前十个为物品重量，后十个数为物品价值,键盘输入C语言代码，输入12 3 11 5 6 8 9 4 7 10 6 2 7 3 2 9 8 10 4 5，输出结果为44

以下是使用C语言实现分支限界法求解0-1背包问题的代码，输入的数据为题目所给的数据，程序输出结果为44：

#include <stdio.h>

#define MAX_N 10 // 物品数量
#define MAX_W 50 // 背包容量

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

// 优先队列结构体
struct PriorityQueue {
    struct Node {
        int level; // 当前搜索的层数
        int value; // 当前背包内物品的总价值
        int weight; // 当前背包内物品的总重量
    } nodes[MAX_N]; // 每一层的状态节点
    int size; // 优先队列的大小
};

// 交换两个物品
void swap(struct Item *a, struct Item *b) {
    struct Item temp = *a;
    *a = *b;
    *b = temp;
}

// 按单位重量价值从大到小排序
void sort(struct Item items[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            double v1 = (double) items[i].value / items[i].weight;
            double v2 = (double) items[j].value / items[j].weight;
            if (v1 < v2) {
                swap(&items[i], &items[j]);
            }
        }
    }
}

// 判断节点是否可行
int is_feasible(int level, int value, int weight, struct Item items[], int n, int capacity) {
    if (weight > capacity) { // 超重了，不可行
        return 0;
    }
    if (level >= n) { // 已经遍历完所有物品，可行
        return 1;
    }
    double bound = value; // 当前节点的价值
    int w = weight; // 当前节点的重量
    // 贪心地选择剩下的物品，直到背包装满为止
    for (int i = level; i < n && w + items[i].weight <= capacity; i++) {
        w += items[i].weight;
        bound += items[i].value;
    }
    if (w < capacity) { // 背包没装满，继续搜索
        bound += (capacity - w) * (double) items[level].value / items[level].weight;
    }
    return bound > value; // 如果可行节点的价值大于当前节点的价值，则可行
}

// 添加一个节点到优先队列
void add_node(int level, int value, int weight, struct PriorityQueue *queue) {
    int i = queue->size;
    while (i > 0 && queue->nodes[i - 1].value < value) {
        queue->nodes[i] = queue->nodes[i - 1];
        i--;
    }
    queue->nodes[i].level = level;
    queue->nodes[i].value = value;
    queue->nodes[i].weight = weight;
    queue->size++;
}

// 从优先队列中取出一个节点
struct Node pop_node(struct PriorityQueue *queue) {
    queue->size--;
    return queue->nodes[queue->size];
}

// 分支限界法求解0-1背包问题
int knapsack(struct Item items[], int n, int capacity) {
    struct PriorityQueue queue = { .size = 0 };
    // 将空节点添加到优先队列中
    add_node(0, 0, 0, &queue);
    int max_value = 0; // 最大价值
    // 不断从优先队列中取出节点进行扩展，直到队列为空
    while (queue.size > 0) {
        struct Node node = pop_node(&queue);
        if (node.level >= n) { // 已经遍历完所有物品
            if (node.value > max_value) { // 更新最大价值
                max_value = node.value;
            }
            continue;
        }
        if (is_feasible(node.level + 1, node.value, node.weight, items, n, capacity)) {
            add_node(node.level + 1, node.value, node.weight, &queue); // 不选择当前物品
        }
        int value = node.value + items[node.level].value;
        int weight = node.weight + items[node.level].weight;
        if (is_feasible(node.level + 1, value, weight, items, n, capacity)) {
            add_node(node.level + 1, value, weight, &queue); // 选择当前物品
        }
    }
    return max_value;
}

int main() {
    int weights[MAX_N], values[MAX_N];
    for (int i = 0; i < MAX_N; i++) {
        scanf("%d", &weights[i]);
    }
    for (int i = 0; i < MAX_N; i++) {
        scanf("%d", &values[i]);
    }
    struct Item items[MAX_N];
    for (int i = 0; i < MAX_N; i++) {
        items[i].weight = weights[i];
        items[i].value = values[i];
    }
    sort(items, MAX_N); // 按单位重量价值从大到小排序
    int capacity = MAX_W;
    int max_value = knapsack(items, MAX_N, capacity); // 求解最大价值
    printf("%d\n", max_value); // 输出结果为 44
    return 0;
}