176 lines
4.6 KiB
C
176 lines
4.6 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
|
|
#define N 3 // 物品数量
|
|
#define CAPACITY 30 // 背包容量
|
|
#define MAX_NODES (N * 2) // 估计的最大节点数
|
|
|
|
// 物品结构体
|
|
typedef struct {
|
|
int weight;
|
|
int value;
|
|
} Item;
|
|
|
|
// 活结点结构体
|
|
typedef struct {
|
|
int level; // 当前节点的层级
|
|
int profit; // 当前节点的价值
|
|
int weight; // 当前节点的重量
|
|
float bound; // 当前节点的上界
|
|
} Node;
|
|
|
|
// 优先队列（最大堆）
|
|
typedef struct {
|
|
Node nodes[MAX_NODES];
|
|
int size;
|
|
} PriorityQueue;
|
|
|
|
// 初始化优先队列
|
|
void initQueue(PriorityQueue* pq) {
|
|
pq->size = 0;
|
|
}
|
|
|
|
// 插入节点到优先队列
|
|
void insert(PriorityQueue* pq, Node node) {
|
|
if (pq->size == MAX_NODES) {
|
|
printf("Priority queue is full.\n");
|
|
return;
|
|
}
|
|
int i = pq->size++;
|
|
while (i > 0 && pq->nodes[(i - 1) / 2].bound < node.bound) {
|
|
pq->nodes[i] = pq->nodes[(i - 1) / 2];
|
|
i = (i - 1) / 2;
|
|
}
|
|
pq->nodes[i] = node;
|
|
}
|
|
|
|
// 删除并返回优先队列的最大元素
|
|
Node removeMax(PriorityQueue* pq) {
|
|
if (pq->size <= 0) {
|
|
printf("Priority queue is empty.\n");
|
|
exit(1);
|
|
}
|
|
Node max = pq->nodes[0];
|
|
pq->nodes[0] = pq->nodes[--pq->size];
|
|
int i = 0;
|
|
while (2 * i + 1 < pq->size) {
|
|
int left = 2 * i + 1;
|
|
int right = 2 * i + 2;
|
|
int largest = i;
|
|
if (left < pq->size && pq->nodes[left].bound > pq->nodes[largest].bound)
|
|
largest = left;
|
|
if (right < pq->size && pq->nodes[right].bound > pq->nodes[largest].bound)
|
|
largest = right;
|
|
if (largest != i) {
|
|
Node temp = pq->nodes[i];
|
|
pq->nodes[i] = pq->nodes[largest];
|
|
pq->nodes[largest] = temp;
|
|
i = largest;
|
|
} else break;
|
|
}
|
|
return max;
|
|
}
|
|
|
|
// 计算节点的上界（bound），这是通过贪心策略估计的最大可能价值
|
|
float calculateBound(Node u, int n, int W, Item items[]) {
|
|
if (u.weight >= W) return 0;
|
|
|
|
int j = u.level + 1;
|
|
float bound = u.profit;
|
|
int totalWeight = u.weight;
|
|
|
|
// 从当前节点继续往下选择物品的贪心解（按单位价值排序）
|
|
while (j < n && totalWeight + items[j].weight <= W) {
|
|
totalWeight += items[j].weight;
|
|
bound += items[j].value;
|
|
j++;
|
|
}
|
|
|
|
if (j < n) {
|
|
bound += (W - totalWeight) * ((float)items[j].value / items[j].weight);
|
|
}
|
|
|
|
return bound;
|
|
}
|
|
|
|
// 比较函数，用于qsort排序
|
|
int compareItems(const void* a, const void* b) {
|
|
Item* itemA = (Item*)a;
|
|
Item* itemB = (Item*)b;
|
|
float unitValueA = (float)itemA->value / itemA->weight;
|
|
float unitValueB = (float)itemB->value / itemB->weight;
|
|
return (unitValueB - unitValueA) > 0 ? 1 : -1;
|
|
}
|
|
|
|
// 0-1 背包问题的分支限界法
|
|
int knapsackBranchAndBound(Item items[], int n, int W) {
|
|
// 按照单位价值对物品进行排序
|
|
qsort(items, n, sizeof(Item), compareItems);
|
|
|
|
PriorityQueue pq;
|
|
initQueue(&pq);
|
|
|
|
// 初始化第一个节点
|
|
Node u = { -1, 0, 0, 0.0 };
|
|
insert(&pq, u);
|
|
|
|
int maxProfit = 0;
|
|
|
|
while (pq.size > 0) {
|
|
// 取出优先队列中的最大元素
|
|
u = removeMax(&pq);
|
|
|
|
// 如果当前节点的 bound 值不大于最大收益，则剪枝
|
|
if (u.bound <= maxProfit) continue;
|
|
|
|
// 尝试将下一个物品放入背包
|
|
Node v = u;
|
|
v.level++;
|
|
|
|
if (v.level < n) {
|
|
// 选择第 v.level 个物品
|
|
if (v.weight + items[v.level].weight <= W) {
|
|
v.weight += items[v.level].weight;
|
|
v.profit += items[v.level].value;
|
|
if (v.profit > maxProfit) {
|
|
maxProfit = v.profit;
|
|
}
|
|
v.bound = calculateBound(v, n, W, items);
|
|
if (v.bound > maxProfit) {
|
|
insert(&pq, v);
|
|
}
|
|
}
|
|
|
|
// 不选择第 v.level 个物品
|
|
v = u;
|
|
v.level++;
|
|
v.bound = calculateBound(v, n, W, items);
|
|
if (v.bound > maxProfit) {
|
|
insert(&pq, v);
|
|
}
|
|
}
|
|
}
|
|
|
|
return maxProfit;
|
|
}
|
|
|
|
int main() {
|
|
// 已经填写的数据
|
|
int weightArr[N] = {16, 15, 15}; // 每个物品的重量
|
|
int valueArr[N] = {45, 25, 25}; // 每个物品的价值
|
|
|
|
// 初始化物品数组
|
|
Item items[N];
|
|
for (int i = 0; i < N; i++) {
|
|
items[i].weight = weightArr[i];
|
|
items[i].value = valueArr[i];
|
|
}
|
|
|
|
// 调用分支限界法求解0-1背包问题
|
|
int maxProfit = knapsackBranchAndBound(items, N, CAPACITY);
|
|
|
|
// 输出最大收益
|
|
printf("Maximum profit: %d\n", maxProfit);
|
|
|
|
return 0;
|
|
} |