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

以下是01背包问题的分支限界法C语言实现：

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

#define MAX_N 1000

typedef struct {
    int v;  // 物品价值
    int w;  // 物品重量
    double bound;  // 价值上界
} Item;

Item items[MAX_N];  // 物品数组
int n;  // 物品数量
int W;  // 背包容量
double maxValue = 0.0;  // 最大价值

// 计算价值上界
double calcBound(int i, int w) {
    double bound = items[i].v;
    int j;
    for (j = i + 1; j < n && w + items[j].w <= W; ++j) {
        bound += items[j].v;
        w += items[j].w;
    }
    if (j < n) {
        bound += (W - w) * (double) items[j].v / items[j].w;
    }
    return bound;
}

// 01背包问题的分支限界法
void knapsack() {
    int i, w = 0;
    double bound = 0.0;
    int stack[MAX_N], top = -1;  // 栈
    stack[++top] = -1;  // 根节点
    while (top >= 0) {
        i = stack[top--];
        if (i == n - 1) {  // 叶节点
            continue;
        }
        if (i == -1) {  // 根节点
            i = 0;
            bound = calcBound(i, w);
        }
        if (w + items[i].w <= W) {  // 左子树
            w += items[i].w;
            maxValue = maxValue > bound ? maxValue : bound;
            stack[++top] = i;
            bound -= items[i].v;
            bound = bound > 0 ? bound : 0;
            stack[++top] = -1;
        }
        bound = calcBound(i + 1, w);  // 右子树
        if (bound > maxValue) {
            stack[++top] = i + 1;
        }
    }
}

int main() {
    int i;
    printf("请输入物品数量和背包容量：");
    scanf("%d%d", &n, &W);
    printf("请输入每个物品的价值和重量：\n");
    for (i = 0; i < n; ++i) {
        scanf("%d%d", &items[i].v, &items[i].w);
    }
    knapsack();
    printf("最大价值为%.2f\n", maxValue);
    return 0;
}

使用方法：

1. 运行程序。
2. 输入物品数量和背包容量。
3. 输入每个物品的价值和重量。
4. 程序输出最大价值。