01背包问题线束回溯法C语言

以下是01背包问题的线束回溯法的C语言实现：

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

#define MAX_N 1000

int n; // 物品数量
int c; // 背包容量
int w[MAX_N]; // 物品重量
int v[MAX_N]; // 物品价值
int max_v; // 最大价值
int cur_w; // 当前重量
int cur_v; // 当前价值
int remain_v[MAX_N]; // 剩余物品的价值
int remain_w[MAX_N]; // 剩余物品的重量

// 计算剩余物品的价值和重量
void calc_remain(int k) {
    int i;
    double bound = cur_v;
    for (i = k; i <= n; i++) {
        remain_w[i] = w[i];
        remain_v[i] = v[i];
    }
    while (i <= n && remain_w[i] <= c - cur_w) {
        cur_w += remain_w[i];
        bound += remain_v[i];
        i++;
    }
    if (i <= n) {
        remain_w[i] = c - cur_w;
        remain_v[i] = remain_w[i] * (double) remain_v[i] / remain_w[i];
        bound += remain_v[i];
    }
}

// 线束回溯
void backtrack(int k) {
    if (k > n) {
        if (cur_v > max_v) {
            max_v = cur_v;
        }
        return;
    }
    calc_remain(k);
    if (cur_v + bound <= max_v) {
        return;
    }
    if (cur_w + w[k] <= c) {
        cur_w += w[k];
        cur_v += v[k];
        backtrack(k + 1);
        cur_w -= w[k];
        cur_v -= v[k];
    }
    if (cur_v + remain_v[k + 1] > max_v) {
        backtrack(k + 1);
    }
}

int main() {
    int i;
    scanf("%d%d", &n, &c);
    for (i = 1; i <= n; i++) {
        scanf("%d%d", &w[i], &v[i]);
    }
    backtrack(1);
    printf("%d\n", max_v);
    return 0;
}