分支限界法解决背包问题c语言

分支限界法是一种解决优化问题的算法，可以用来解决背包问题。下面是一个使用C语言实现分支限界法解决背包问题的示例代码：

#include <stdio.h>

#define MAX_N 100 // 背包中物品的最大数量

typedef struct {
    int weight; // 物品的重量
    int value; // 物品的价值
} Item;

int max_value = 0; // 最大价值
int best_solution[MAX_N]; // 最优解
int current_solution[MAX_N]; // 当前解
int current_weight = 0; // 当前解的总重量
int current_value = 0; // 当前解的总价值

// 计算剩余物品的上界
int calculate_upper_bound(Item items[], int n, int capacity, int level) {
    int upper_bound = current_value;
    int total_weight = current_weight;
    int i = level + 1;
    
    // 将剩余物品按单位价值降序排序
    for (; i < n; i++) {
        if (total_weight + items[i].weight <= capacity) {
            total_weight += items[i].weight;
            upper_bound += items[i].value;
        } else {
            break;
        }
    }
    
    // 考虑部分装入最后一个物品的情况
    if (i < n) {
        upper_bound += (capacity - total_weight) * items[i].value / items[i].weight;
    }
    
    return upper_bound;
}

// 回溯搜索
void backtrack(Item items[], int n, int capacity, int level) {
    if (level == n) {
        // 更新最大价值和最优解
        if (current_value > max_value) {
            max_value = current_value;
            for (int i = 0; i < n; i++) {
                best_solution[i] = current_solution[i];
            }
        }
        return;
    }
    
    // 不选择当前物品
    int upper_bound = calculate_upper_bound(items, n, capacity, level);
    if (upper_bound > max_value) {
        backtrack(items, n, capacity, level + 1);
    }
    
    // 选择当前物品
    if (current_weight + items[level].weight <= capacity) {
        current_weight += items[level].weight;
        current_value += items[level].value;
        current_solution[level] = 1;
        upper_bound = calculate_upper_bound(items, n, capacity, level);
        if (upper_bound > max_value) {
            backtrack(items, n, capacity, level + 1);
        }
        current_weight -= items[level].weight;
        current_value -= items[level].value;
        current_solution[level] = 0;
    }
}

int main() {
    int n; // 物品的数量
    int capacity; // 背包的容量
    Item items[MAX_N]; // 物品数组
    
    // 输入物品的数量和背包的容量
    printf("Enter the number of items: ");
    scanf("%d", &n);
    printf("Enter the capacity of the knapsack: ");
    scanf("%d", &capacity);
    
    // 输入每个物品的重量和价值
    printf("Enter the weight and value of each item:\n");
    for (int i = 0; i < n; i++) {
        printf("Item %d: ", i + 1);
        scanf("%d %d", &items[i].weight, &items[i].value);
    }
    
    // 初始化最优解和当前解
    for (int i = 0; i < n; i++) {
        best_solution[i] = 0;
        current_solution[i] = 0;
    }
    
    // 使用分支限界法求解背包问题
    backtrack(items, n, capacity, 0);
    
    // 输出最大价值和最优解
    printf("Max value: %d\n", max_value);
    printf("Best solution: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", best_solution[i]);
    }
    printf("\n");
    
    return 0;
}