分支限界法 01背包c语言,算法笔记分支限界法01背包问题

好的，我明白了。关于分支限界法的01背包问题，我可以给你一些思路和算法实现的笔记。

首先，01背包问题是指在有限的背包容量下，从给定的一组物品中选取一些物品放入背包中，使得背包中物品的总价值最大。而分支限界法则是一种解决优化问题的方法，它通过限制问题的搜索空间，逐步缩小问题的解空间，从而获得最优解。

对于01背包问题，我们可以采用以下步骤：

1. 构造一个搜索树，根节点代表空背包，每个节点代表向背包中添加一个物品或不添加物品的决策。
2. 对于每个节点，计算当前背包中物品的总价值以及还有多少容量可以使用。
3. 对于每个未被扩展的节点，计算它的上界价值（即背包在剩余容量中所能获得的最大价值），并按照上界价值从大到小排序。
4. 选择上界价值最大的节点进行扩展，即添加一个物品或不添加物品的两种决策分别扩展出两个子节点。
5. 不断重复步骤3和4，直到搜索树中的所有节点都被扩展完毕。

以下是一个简单的C语言实现，其中用一个结构体表示每个节点的状态，通过一个优先队列来实现按照上界价值排序的功能：

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

#define MAX_N 1000

int n, c;
int w[MAX_N], v[MAX_N];
int max_v;

typedef struct Node {
    int level;
    int value;
    int weight;
    int bound;
} Node;

typedef struct PriorityQueue {
    Node* arr[MAX_N];
    int size;
} PriorityQueue;

PriorityQueue* createPriorityQueue() {
    PriorityQueue* q = (PriorityQueue*)malloc(sizeof(PriorityQueue));
    q->size = 0;
    return q;
}

void push(PriorityQueue* q, Node* node) {
    q->arr[q->size++] = node;
    int i = q->size - 1;
    while (i > 0 && q->arr[i]->bound > q->arr[(i - 1) / 2]->bound) {
        Node* temp = q->arr[i];
        q->arr[i] = q->arr[(i - 1) / 2];
        q->arr[(i - 1) / 2] = temp;
        i = (i - 1) / 2;
    }
}

Node* pop(PriorityQueue* q) {
    Node* node = q->arr[0];
    q->arr[0] = q->arr[--q->size];
    int i = 0;
    while (i * 2 + 1 < q->size) {
        int j = i * 2 + 1;
        if (j + 1 < q->size && q->arr[j + 1]->bound > q->arr[j]->bound) {
            j++;
        }
        if (q->arr[i]->bound < q->arr[j]->bound) {
            Node* temp = q->arr[i];
            q->arr[i] = q->arr[j];
            q->arr[j] = temp;
            i = j;
        } else {
            break;
        }
    }
    return node;
}

void solve() {
    PriorityQueue* q = createPriorityQueue();
    Node* root = (Node*)malloc(sizeof(Node));
    root->level = 0;
    root->value = 0;
    root->weight = 0;
    root->bound = max_v;
    push(q, root);
    while (q->size > 0) {
        Node* node = pop(q);
        if (node->bound <= max_v || node->level == n) {
            continue;
        }
        Node* left = (Node*)malloc(sizeof(Node));
        left->level = node->level + 1;
        left->value = node->value + v[left->level];
        left->weight = node->weight + w[left->level];
        if (left->weight <= c) {
            left->bound = left->value + (max_v - left->value) * 1.0 / w[left->level];
            if (left->value > max_v) {
                max_v = left->value;
            }
            push(q, left);
        }
        Node* right = (Node*)malloc(sizeof(Node));
        right->level = node->level + 1;
        right->value = node->value;
        right->weight = node->weight;
        right->bound = right->value + (max_v - right->value) * 1.0 / w[right->level];
        push(q, right);
    }
}

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

希望这些笔记能够对你有所帮助，如果有任何问题，欢迎随时问我。