装载问题分支限界法用c语言实现代码
时间: 2023-10-26 15:06:07 浏览: 75
装载问题是一个经典的组合优化问题,分支限界法是其中一种常见的求解方法。下面是使用C语言实现装载问题分支限界法的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 1000 // 最大物品数量
#define MAX_C 1000 // 最大容量
// 物品结构体
struct Item {
int weight; // 重量
int profit; // 价值
};
// 节点结构体
struct Node {
int level; // 当前节点所在的层数
int profit; // 当前价值
int weight; // 当前重量
int bound; // 当前上界
};
// 全局变量
int n, c; // 物品数量和背包容量
int max_profit; // 最优解
int max_weight; // 最优解对应的重量
struct Item items[MAX_N]; // 所有物品
// 比较函数,用于qsort排序
int cmp(const void *a, const void *b) {
double r1 = ((struct Item *)a)->profit / (double)((struct Item *)a)->weight;
double r2 = ((struct Item *)b)->profit / (double)((struct Item *)b)->weight;
return (r2 - r1) > 0 ? 1 : -1;
}
// 计算当前节点的上界
int bound(struct Node node) {
int remaining_weight = c - node.weight; // 剩余容量
int bound = node.profit; // 上界初始化为当前价值
int i = node.level;
while (i < n && remaining_weight > 0) { // 遍历所有剩余的物品,直到装满背包或者没有物品了
if (remaining_weight >= items[i].weight) { // 如果当前物品能够全部装入背包
bound += items[i].profit; // 加上当前物品的价值
remaining_weight -= items[i].weight; // 减去当前物品的重量
} else { // 如果当前物品只能装一部分
bound += (remaining_weight / (double)items[i].weight) * items[i].profit; // 加上部分价值
remaining_weight = 0; // 背包已经装满,跳出循环
}
i++;
}
return bound;
}
// 装载问题分支限界法
void branch_and_bound() {
// 初始化根节点
struct Node root = { -1, 0, 0, 0 };
root.bound = bound(root);
// 使用堆栈保存所有未扩展的节点
struct Node stack[MAX_N * 2];
int top = 0;
stack[top++] = root;
while (top > 0) {
// 取出当前最优的节点进行扩展
struct Node node = stack[--top];
// 如果当前节点的上界小于等于最优解,或者当前节点已经扩展完毕,则跳过
if (node.bound > max_profit && node.level < n - 1) {
// 扩展左节点(不装当前物品)
struct Node left = { node.level + 1, node.profit, node.weight, 0 };
left.bound = bound(left);
stack[top++] = left;
// 扩展右节点(装当前物品)
struct Node right = { node.level + 1, node.profit + items[node.level + 1].profit, node.weight + items[node.level + 1].weight, 0 };
right.bound = bound(right);
if (right.weight <= c && right.profit > max_profit) { // 如果右节点符合条件,则更新最优解
max_profit = right.profit;
max_weight = right.weight;
}
if (right.bound > max_profit) { // 如果右节点的上界大于最优解,则加入堆栈
stack[top++] = right;
}
}
}
}
int main() {
// 读入输入
scanf("%d%d", &n, &c);
for (int i = 0; i < n; i++) {
scanf("%d%d", &items[i].weight, &items[i].profit);
}
// 按单位重量价值排序
qsort(items, n, sizeof(struct Item), cmp);
// 使用分支限界法求解
branch_and_bound();
// 输出结果
printf("Max profit: %d\n", max_profit);
printf("Max weight: %d\n", max_weight);
return 0;
}
```
主要思路是使用一个堆栈保存所有未扩展的节点,每次取出堆栈中的最优节点进行扩展,直到堆栈为空。在扩展节点时,先计算当前节点的上界,如果上界小于等于当前最优解,则跳过该节点;否则,分别扩展左节点(不装当前物品)和右节点(装当前物品),并分别计算它们的上界。如果右节点符合条件,则更新最优解;如果右节点的上界大于当前最优解,则将其加入堆栈中。