优先队列式分枝限界法求解最优装载问题 - C语言实现

{ "实验目的": "使用优先队列式分枝限界法求解最优装载问题。", "实验环境": "C语言编程环境", "实验内容": "\n1. 输入集装箱个数n、每个集装箱的重量w和限重W。\n2. 使用优先队列保存当前的装载状态，包括已装载的集装箱数量和当前总重量。\n3. 初始化最优装载方案的集装箱数量为最大值，当前最优总重量为0。\n4. 循环遍历每个集装箱：\n - 如果当前总重量加上当前集装箱的重量小于等于限重W，则将当前集装箱装载到当前状态中，并计算当前总重量。\n - 如果当前状态的集装箱数量小于最优装载方案的集装箱数量，则更新最优装载方案的集装箱数量和当前最优总重量。\n - 如果当前总重量加上当前集装箱的重量大于限重W，则不装载当前集装箱。\n5. 输出最优装载方案的集装箱数量和当前最优总重量。", "算法设计 (伪代码)": "\n1. 输入集装箱个数n、每个集装箱的重量w和限重W。\n2. 使用优先队列保存当前的装载状态，包括已装载的集装箱数量和当前总重量。\n3. 初始化最优装载方案的集装箱数量为最大值，当前最优总重量为0。\n4. 将初始状态（装载的集装箱数量为0，当前总重量为0）插入优先队列。\n5. while(优先队列不为空)：\n 1. 取出当前状态。\n 2. 如果当前状态的集装箱数量小于最优装载方案的集装箱数量：\n - 循环遍历每个集装箱：\n - 如果当前总重量加上当前集装箱的重量小于等于限重W，则将当前集装箱装载到当前状态中，并计算当前总重量。\n - 如果当前状态的集装箱数量加上1小于最优装载方案的集装箱数量，则将当前状态插入优先队列。\n 3. 如果当前总重量加上当前集装箱的重量大于限重W，则不装载当前集装箱。\n6. 输出最优装载方案的集装箱数量和当前最优总重量。\n", "程序清单": "c\n#include <stdio.h>\n#include <stdlib.h>\n\n#define MAX_WEIGHT 10000 // 最大重量\n\n// 定义装载状态的结构体\ntypedef struct {\n int num; // 已装载的集装箱数量\n double weight; // 当前总重量\n} LoadState;\n\n// 定义优先队列的节点结构体\ntypedef struct {\n LoadState state; // 装载状态\n double bound; // 当前状态的上界\n} Node;\n\n// 定义优先队列的结构体\ntypedef struct {\n Node* nodes; // 节点数组\n int maxSize; // 最大容量\n int size; // 当前大小\n} PriorityQueue;\n\n// 初始化优先队列\nPriorityQueue* initPriorityQueue(int maxSize) {\n PriorityQueue* queue = (PriorityQueue*)malloc(sizeof(PriorityQueue));\n queue->nodes = (Node*)malloc(sizeof(Node) * maxSize);\n queue->maxSize = maxSize;\n queue->size = 0;\n return queue;\n}\n\n// 销毁优先队列\nvoid destroyPriorityQueue(PriorityQueue* queue) {\n free(queue->nodes);\n free(queue);\n}\n\n// 插入节点到优先队列\nvoid insertNode(PriorityQueue* queue, Node node) {\n int i;\n for (i = 0; i < queue->size; i++) {\n if (node.bound > queue->nodes[i].bound) {\n break;\n }\n }\n for (int j = queue->size - 1; j >= i; j--) {\n queue->nodes[j + 1] = queue->nodes[j];\n }\n queue->nodes[i] = node;\n queue->size++;\n}\n\n// 取出优先队列的最小节点\nNode popMinNode(PriorityQueue* queue) {\n Node minNode = queue->nodes[0];\n for (int i = 1; i < queue->size; i++) {\n queue->nodes[i - 1] = queue->nodes[i];\n }\n queue->size--;\n return minNode;\n}\n\n// 获取当前状态的上界\ndouble getBound(LoadState state, double* weights, int n, double W) {\n double bound = state.weight;\n int i = state.num;\n while (i < n && weights[i] <= W - state.weight) {\n bound += weights[i];\n W -= weights[i];\n i++;\n }\n if (i < n) {\n bound += weights[i] * (W / weights[i]);\n }\n return bound;\n}\n\n// 优先队列式分枝限界法求解最优装载问题\nvoid solveLoadingProblem(int n, double* weights, double W) {\n PriorityQueue* queue = initPriorityQueue(n);\n LoadState initState = {0, 0};\n Node initNode = {initState, getBound(initState, weights, n, W)};\n insertNode(queue, initNode);\n\n int bestNum = n + 1;\n double bestWeight = 0;\n\n while (queue->size > 0) {\n Node node = popMinNode(queue);\n LoadState state = node.state;\n\n if (state.num < bestNum) {\n for (int i = state.num; i < n; i++) {\n if (state.weight + weights[i] <= W) {\n LoadState newState = {state.num + 1, state.weight + weights[i]};\n Node newNode = {newState, getBound(newState, weights, n, W)};\n insertNode(queue, newNode);\n }\n }\n }\n\n if (state.num < bestNum && state.weight > bestWeight) {\n bestNum = state.num;\n bestWeight = state.weight;\n }\n }\n\n printf("最优装载方案的集装箱数量：%d\n", bestNum);\n printf("当前最优总重量：%f\n", bestWeight);\n\n destroyPriorityQueue(queue);\n}\n\nint main() {\n int n;\n printf("请输入集装箱个数：");\n scanf("%d", &n);\n\n double* weights = (double*)malloc(sizeof(double) * n);\n printf("请输入每个集装箱的重量：");\n for (int i = 0; i < n; i++) {\n scanf("%lf", &weights[i]);\n }\n\n double W;\n printf("请输入限重：");\n scanf("%lf", &W);\n\n solveLoadingProblem(n, weights, W);\n\n free(weights);\n return 0;\n}\n