解0/1背包箱问题。分别用fifo队列分支限界法实现。用c实现

0/1背包问题是一个经典的动态规划问题，分支限界法是一种求解这类问题的常用方法。下面分别用fifo队列分支限界法实现0/1背包问题，并用C语言实现。

1. fifo队列分支限界法

（1）算法思想

fifo队列分支限界法是一种广度优先搜索算法，其基本思想是：将所有可行的扩展节点按照某种规则（如估价函数）排序后加入队列，然后依次取出队首节点进行扩展，直到找到最优解为止。

在0/1背包问题中，每个节点表示一个物品的选择方案，每个节点分为两种情况：

- 选择当前物品，将其放入背包中；
- 不选择当前物品，直接跳过。

对于每个节点，我们都可以计算出其所能获得的价值上限，即当前物品及其后面的物品所能贡献的最大价值。这个上限就是估价函数，我们可以按照这个上限对所有节点进行排序，并将其加入队列中。

在进行扩展时，我们可以根据当前节点的选择情况，计算出扩展节点的价值上限，并将其加入队列中。直到队列为空或者找到最优解为止。

（2）算法流程

1. 初始化队列，将初始节点加入队列；
2. 从队首取出节点，并进行扩展；
3. 对于每个扩展节点，计算其价值上限，并将其加入队列；
4. 对所有节点按照价值上限排序，并将其加入队列；
5. 如果队列为空，则搜索结束；
6. 如果当前节点的价值上限小于当前最优解，则将其加入队列；
7. 如果当前节点是叶子节点，则更新最优解；
8. 回到步骤2，继续搜索。

（3）算法实现

下面是用C语言实现fifo队列分支限界法的代码：

相关问题

分支限界法先进先出求解01背包

分支限界法是一种动态规划方法，用于解决组合优化问题，如0/1背包问题。在这个问题中，我们需要在给定的一组物品中选择一些放入背包，每个物品有自己的价值和重量限制，目标是在不超过背包容量的前提下最大化总价值。

先进先出（First-In-First-Out, FIFO）版本的分支限界法通常应用于背包问题，它采用了一个队列数据结构来存储待探索的状态。算法步骤如下：

1. **初始化**：创建一个空队列，并将初始状态（没有选择任何物品，背包容量未消耗）放入队列。

2. **搜索过程**：
- **从队首取出状态**：取队首状态，如果当前状态的价值大于已知的最大值，则更新最大价值。
- **生成子状态**：对于当前物品，有两种选择：要么不选（前进），要么选（并添加下一个更小重量的物品，如果有的话）。分别对这两种情况生成新的子状态。
- **剪枝**：如果新产生的子状态的价值小于当前状态加上剩余背包容量可以携带的最大物品价值，则无需进一步处理，因为不会有更好的结果。
- **插入子状态**：将有效的子状态按照FIFO原则插入队列的末尾，较小的优先级更高，表示它们更接近最终解决方案。

3. **结束条件**：当队列为空或无法找到更大的解时，停止搜索，返回当前最佳状态下的最大价值。

C语言求解0/1背包箱问题。分别用先进先出队列分支限界法和优先队列分支限界法实现。

首先，0/1背包问题是一种经典的动态规划问题，其思路是将问题分解成子问题，然后逐步求解。

先进先出队列分支限界法：

代码实现如下：

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

#define N 4
#define C 8

typedef struct {
    int level;  // 当前节点所在的层数
    int profit; // 当前节点的价值
    int weight; // 当前节点的重量
    int bound;  // 当前节点的上界
} Node;

typedef struct {
    Node *queue[N * 10]; // 先进先出队列
    int front, rear;
} FIFO_Queue;

void init_queue(FIFO_Queue *q) {
    q->front = q->rear = 0;
}

int is_empty_queue(FIFO_Queue *q) {
    return q->front == q->rear;
}

int is_full_queue(FIFO_Queue *q) {
    return (q->rear + 1) % (N * 10) == q->front;
}

void enqueue(FIFO_Queue *q, Node *node) {
    if (!is_full_queue(q)) {
        q->queue[q->rear] = node;
        q->rear = (q->rear + 1) % (N * 10);
    }
}

Node *dequeue(FIFO_Queue *q) {
    if (!is_empty_queue(q)) {
        Node *node = q->queue[q->front];
        q->front = (q->front + 1) % (N * 10);
        return node;
    }
    return NULL;
}

void swap(Node *a, Node *b) {
    Node temp = *a;
    *a = *b;
    *b = temp;
}

// 用于排序的比较函数
int cmp_node(const void *a, const void *b) {
    Node *n1 = *(Node **)a;
    Node *n2 = *(Node **)b;
    return n2->bound - n1->bound;
}

int max(int a, int b) {
    return a > b ? a : b;
}

int knapsack(int *weight, int *profit, int n) {
    FIFO_Queue queue;
    init_queue(&queue);

    Node *root = (Node *)malloc(sizeof(Node));
    root->level = root->profit = root->weight = 0;
    root->bound = 0;

    int max_profit = 0;

    enqueue(&queue, root);

    while (!is_empty_queue(&queue)) {
        Node *node = dequeue(&queue);

        if (node->level == n) {
            if (node->profit > max_profit) {
                max_profit = node->profit;
            }
            continue;
        }

        Node *left = (Node *)malloc(sizeof(Node));
        left->level = node->level + 1;
        left->profit = node->profit + profit[left->level - 1];
        left->weight = node->weight + weight[left->level - 1];

        if (left->weight <= C && left->profit > max_profit) {
            max_profit = left->profit;
        }

        if (left->bound > max_profit) {
            enqueue(&queue, left);
        }

        Node *right = (Node *)malloc(sizeof(Node));
        right->level = node->level + 1;
        right->profit = node->profit;
        right->weight = node->weight;

        if (right->bound > max_profit) {
            enqueue(&queue, right);
        }
    }

    return max_profit;
}

int main() {
    int weight[N] = {2, 3, 4, 5};
    int profit[N] = {3, 4, 5, 6};

    printf("最大价值为：%d\n", knapsack(weight, profit, N));

    return 0;
}

优先队列分支限界法：

代码实现如下：

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

#define N 4
#define C 8

typedef struct {
    int level;  // 当前节点所在的层数
    int profit; // 当前节点的价值
    int weight; // 当前节点的重量
    int bound;  // 当前节点的上界
} Node;

typedef struct {
    Node **queue; // 优先队列
    int size;
} PQ;

void init_pq(PQ *pq) {
    pq->queue = (Node **)malloc(N * sizeof(Node *));
    pq->size = 0;
}

int is_empty_pq(PQ *pq) {
    return pq->size == 0;
}

void enqueue(PQ *pq, Node *node) {
    pq->queue[pq->size++] = node;
}

Node *dequeue(PQ *pq) {
    int min_idx = 0;
    for (int i = 1; i < pq->size; i++) {
        if (pq->queue[i]->bound > pq->queue[min_idx]->bound) {
            min_idx = i;
        }
    }
    Node *node = pq->queue[min_idx];
    pq->queue[min_idx] = pq->queue[pq->size - 1];
    pq->size--;
    return node;
}

void swap(Node *a, Node *b) {
    Node temp = *a;
    *a = *b;
    *b = temp;
}

// 用于排序的比较函数
int cmp_node(const void *a, const void *b) {
    Node *n1 = *(Node **)a;
    Node *n2 = *(Node **)b;
    return n2->bound - n1->bound;
}

int max(int a, int b) {
    return a > b ? a : b;
}

int bound(Node *node, int *weight, int *profit, int n) {
    if (node->weight >= C) {
        return 0;
    }

    int j = node->level;
    int totweight = node->weight;
    int result = node->profit;

    while (j < n && totweight + weight[j] <= C) {
        totweight += weight[j];
        result += profit[j];
        j++;
    }

    if (j < n) {
        result += (C - totweight) * profit[j] / weight[j];
    }

    return result;
}

int knapsack(int *weight, int *profit, int n) {
    PQ pq;
    init_pq(&pq);

    Node *root = (Node *)malloc(sizeof(Node));
    root->level = root->profit = root->weight = 0;
    root->bound = bound(root, weight, profit, n);

    int max_profit = 0;

    enqueue(&pq, root);

    while (!is_empty_pq(&pq)) {
        Node *node = dequeue(&pq);

        if (node->level == n) {
            if (node->profit > max_profit) {
                max_profit = node->profit;
            }
            continue;
        }

        Node *left = (Node *)malloc(sizeof(Node));
        left->level = node->level + 1;
        left->profit = node->profit + profit[left->level - 1];
        left->weight = node->weight + weight[left->level - 1];
        left->bound = bound(left, weight, profit, n);

        if (left->weight <= C && left->profit > max_profit) {
            max_profit = left->profit;
        }

        if (left->bound > max_profit) {
            enqueue(&pq, left);
        }

        Node *right = (Node *)malloc(sizeof(Node));
        right->level = node->level + 1;
        right->profit = node->profit;
        right->weight = node->weight;
        right->bound = bound(right, weight, profit, n);

        if (right->bound > max_profit) {
            enqueue(&pq, right);
        }
    }

    return max_profit;
}

int main() {
    int weight[N] = {2, 3, 4, 5};
    int profit[N] = {3, 4, 5, 6};

    printf("最大价值为：%d\n", knapsack(weight, profit, N));

    return 0;
}