利用队列分支限界法求解0/1背包问题c++源码
时间: 2023-06-13 14:05:40 浏览: 77
以下是使用队列分支限界法求解0/1背包问题的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 1000
typedef struct {
int profit;
int weight;
float bound;
int level;
} Node;
typedef struct {
Node nodes[MAX_SIZE];
int front;
int rear;
} Queue;
Queue *create_queue() {
Queue *q = (Queue *) malloc(sizeof(Queue));
q->front = q->rear = -1;
return q;
}
int is_empty(Queue *q) {
return q->front == -1;
}
void enqueue(Queue *q, Node n) {
if (q->front == -1) {
q->front = q->rear = 0;
q->nodes[q->rear] = n;
} else {
q->rear++;
q->nodes[q->rear] = n;
}
}
Node dequeue(Queue *q) {
Node n = q->nodes[q->front];
if (q->front == q->rear) {
q->front = q->rear = -1;
} else {
q->front++;
}
return n;
}
int max(int a, int b) {
return a > b ? a : b;
}
float bound(Node n, int n_items, int max_weight, int *profits, int *weights) {
int i, j;
int remaining_weight = max_weight - n.weight;
float bound = n.profit;
i = n.level + 1;
while (i < n_items && remaining_weight > 0) {
if (remaining_weight >= weights[i]) {
remaining_weight -= weights[i];
bound += profits[i];
} else {
bound += profits[i] * ((float) remaining_weight / weights[i]);
remaining_weight = 0;
}
i++;
}
return bound;
}
int knapsack(int n_items, int max_weight, int *profits, int *weights) {
Queue *q = create_queue();
Node root, curr;
int max_profit = 0;
root.profit = 0;
root.weight = 0;
root.level = -1;
root.bound = bound(root, n_items, max_weight, profits, weights);
enqueue(q, root);
while (!is_empty(q)) {
curr = dequeue(q);
if (curr.level == n_items - 1) {
continue;
}
Node left, right;
left.level = curr.level + 1;
left.weight = curr.weight + weights[left.level];
left.profit = curr.profit + profits[left.level];
if (left.weight <= max_weight && left.profit > max_profit) {
max_profit = left.profit;
}
left.bound = bound(left, n_items, max_weight, profits, weights);
if (left.bound > max_profit) {
enqueue(q, left);
}
right.level = curr.level + 1;
right.weight = curr.weight;
right.profit = curr.profit;
right.bound = bound(right, n_items, max_weight, profits, weights);
if (right.bound > max_profit) {
enqueue(q, right);
}
}
return max_profit;
}
int main() {
int n_items, max_weight, i;
int profits[MAX_SIZE], weights[MAX_SIZE];
printf("Enter number of items: ");
scanf("%d", &n_items);
printf("Enter max weight: ");
scanf("%d", &max_weight);
printf("Enter profits and weights of each item: \n");
for (i = 0; i < n_items; i++) {
scanf("%d %d", &profits[i], &weights[i]);
}
printf("Max profit = %d\n", knapsack(n_items, max_weight, profits, weights));
return 0;
}
```
在该代码中,我们使用了一个队列来存储待扩展的节点。我们从根节点开始,计算其上界,然后将其加入队列。接着,我们取出队列中的节点进行扩展,生成其左右子节点,并计算它们的上界。如果左节点的上界大于当前最大收益,则将其加入队列。如果右节点的上界大于当前最大收益,则将其加入队列。当队列为空时,我们就找到了最大收益。
注意,我们在计算节点的上界时,采用了贪心策略,即每次选择能够获得最大单位收益的物品,直到背包被装满为止。这样得到的上界是一个下界的估计,因此可以有效地剪枝。