企业官网建设流程全解析

#include<iostream> #include<cmath> using namespace std; // ===================== 全局常量定义 ===================== // 极小值，用于边界比较 const float epsilon = 1e-6f; // 模板零值，适配不同数值类型 template<class T> T Zero = T(0); // 优先队列最大容量（可根据物品数调整） const int mSize = 1000; // ===================== 状态空间树结点结构 ===================== /** * @brief 状态空间树结点，记录每个结点的双亲关系与左右孩子标记 * 用于最后回溯生成最优解（选/不选物品） */ struct Node { Node* parent; // 指向双亲结点的指针 bool left; // true=左孩子(选当前物品)，false=右孩子(不选当前物品) /** * @brief 结点构造函数 * @param par 双亲结点指针 * @param lft 是否为左孩子 */ Node(Node* par, bool lft) { parent = par; left = lft; } }; // ===================== 优先队列结点结构 ===================== /** * @brief 优先队列存储的结点，包含分枝限界所需全部信息 * @tparam T 收益类型（int/double 等） */ template<class T> struct pqNode { float cu; // 背包剩余载重 T profit; // 当前已获得收益 T UBB; // 上界函数值（剪枝核心） int level; // 当前处理到第几个物品（根为 0） Node* ptr; // 指向状态空间树对应结点 /** * @brief 类型转换重载：用于优先队列优先级比较 * @return 上界值 UBB，优先队列按 UBB 降序排列 */ operator T() const { return UBB; } // 默认构造 pqNode() {} /** * @brief 构造函数 * @param cap 剩余容量 * @param prof 当前收益 * @param ub 上界值 * @param lev 当前层数 * @param p 状态树结点指针 */ pqNode(float cap, T prof, T ub, int lev, Node* p) { cu = cap; profit = prof; UBB = ub; level = lev; ptr = p; } }; // ===================== 最大优先队列（完善实现） ===================== /** * @brief 最大堆实现的优先队列，优先级由 UBB 决定（大的优先出队） * @tparam T 队列元素类型 */ template<class T> class prioQueue { private: T* heap; // 堆数组 int capacity; // 容量 int size; // 当前元素个数 // 向上调整（插入） void siftUp(int i) { T temp = heap[i]; while (i > 1 && temp > heap[i / 2]) { heap[i] = heap[i / 2]; i /= 2; } heap[i] = temp; } // 向下调整（删除堆顶） void siftDown(int i) { int child; T temp = heap[i]; while (2 * i <= size) { child = 2 * i; if (child < size && heap[child + 1] > heap[child]) child++; if (heap[child] > temp) { heap[i] = heap[child]; i = child; } else break; } heap[i] = temp; } public: // 构造 prioQueue(int cap) { capacity = cap; heap = new T[capacity + 1]; // 堆从 1 号位置开始 size = 0; } // 析构 ~prioQueue() { delete[] heap; } // 判断空 bool IsEmpty() const { return size == 0; } // 入队 void Append(const T& x) { if (size == capacity) { cout << "优先队列已满！" << endl; return; } heap[++size] = x; siftUp(size); } // 出队（取最大优先级元素） bool Serve(T& x) { if (IsEmpty()) return false; x = heap[1]; heap[1] = heap[size--]; siftDown(1); return true; } }; // ===================== 0/1 背包 LC 分枝限界类 ===================== /** * @brief 0/1 背包问题 —— 最小代价优先（LC）分枝限界解法 * @tparam T 收益类型（int / double） */ template <class T> class Knapsack { public: /** * @brief 构造函数：初始化背包参数 * @param prof 物品收益数组 * @param wei 物品重量数组 * @param mm 背包最大载重 * @param len 物品数量 */ Knapsack(T* prof, float* wei, float mm, int len); /** * @brief LC 分枝限界主算法：求解最优收益 * @return 最大收益 */ T LCBB(); /** * @brief 根据状态树回溯生成最优解数组 * @param x 解数组 x[i]=1 表示选第 i 个物品，0 不选 */ void GenerateAns(int* x); private: /** * @brief 计算当前结点的 下界 LBB 和 上界 UBB * @param cp 当前总收益 * @param cw 当前已用重量 * @param k 当前处理到第 k 个物品 * @param LBB 返回计算的下界 * @param UBB 返回计算的上界 */ void LUBound(T cp, float cw, int k, T& LBB, T& UBB); T* p; // 物品收益数组 float* w; // 物品重量数组 float m; // 背包容量 int n; // 物品总数 Node* ans; // 最优解结点（用于回溯） Node* root; // 状态空间树根结点 }; // ===================== 上下界函数实现 ===================== /** * 上界 UBB：假设物品可分割，求最大收益（松弛上界） * 下界 LBB：只装完整物品，求保守收益 */ template<class T> void Knapsack<T>::LUBound(T cp, float cw, int k, T& LBB, T& UBB) { LBB = cp; // 下界初始化为当前已获得收益 float c = cw; // 当前剩余容量 UBB = cp; // 上界初始化 // 1. 计算上界（可分割背包） for (int i = k; i < n; i++) { if (c >= w[i]) { // 能完整装入，直接加 UBB += p[i]; c -= w[i]; } else { // 不能完整装入，分割装入 UBB += c * p[i] / w[i]; break; } } // 2. 计算下界（只装完整物品） c = cw; LBB = cp; for (int i = k; i < n; i++) { if (c >= w[i]) { LBB += p[i]; c -= w[i]; } } } // ===================== LC 分枝限界主算法实现 ===================== template<class T> T Knapsack<T>::LCBB() { Node* child; // 孩子结点指针 Node* E; // 当前扩展结点 T LBB, UBB, L; // 下界、上界、当前最优值 ans = NULL; // 最优解结点初始空 // 初始化优先队列 prioQueue<pqNode<T>> pq(mSize); // 建立根结点（无父亲，不是左孩子） root = new Node(NULL, false); // 计算根结点上下界 LUBound(0, m, 0, LBB, UBB); // 根结点入队 pqNode<T> e(m, 0, UBB, 0, root); // 最优值初始化为 下界-极小值 L = LBB - epsilon; // 迭代扩展结点 do { // 取出当前扩展结点信息 int k = e.level; float cap = e.cu; T prof = e.profit; E = e.ptr; // ---------------- 叶子结点：更新最优解 ---------------- if (k == n && prof > L) { L = prof; ans = E; continue; } // ---------------- 分枝 1：左孩子 = 选第 k 个物品 ---------------- if (cap >= w[k]) { child = new Node(E, true); // 构造新结点并入队 pqNode<T> leftNode(cap - w[k], prof + p[k], 0, k + 1, child); // 计算新结点上下界 LUBound(leftNode.profit, leftNode.cu, k + 1, LBB, UBB); leftNode.UBB = UBB; pq.Append(leftNode); } // ---------------- 分枝 2：右孩子 = 不选第 k 个物品 ---------------- LUBound(prof, cap, k + 1, LBB, UBB); // 上界 > 当前最优值，才值得扩展（剪枝） if (UBB > L) { child = new Node(E, false); pqNode<T> rightNode(cap, prof, UBB, k + 1, child); pq.Append(rightNode); // 更新最优下界 if (L < LBB - epsilon) L = LBB - epsilon; } } while (!pq.IsEmpty() && pq.Serve(e) && e.UBB > L); return L; } // ===================== 构造函数实现 ===================== template<class T> Knapsack<T>::Knapsack(T* prof, float* wei, float mm, int len) { n = len; p = prof; w = wei; m = mm; ans = root = NULL; } // ===================== 生成最优解数组实现 ===================== template<class T> void Knapsack<T>::GenerateAns(int* x) { // 初始化解数组 for (int i = 0; i < n; i++) x[i] = 0; Node* cur = ans; int idx = n - 1; // 从最优解结点向上回溯到根 while (cur != root && cur != NULL && idx >= 0) { if (cur->left) x[idx] = 1; // 左孩子 = 选当前物品 cur = cur->parent; idx--; } } // ===================== 测试主函数 ===================== int main() { // 物品按 单位重量收益 降序排序！！！（必须） // 物品 0: p=60, w=10 → 6 // 物品 1: p=100, w=20 →5 // 物品 2: p=120, w=30 →4 int p[] = {60, 100, 120}; float w[] = {10, 20, 30}; float m = 50; int n = 3; // 创建背包对象 Knapsack<int> ks(p, w, m, n); // 求解最大收益 int maxProfit = ks.LCBB(); cout << "0/1 背包最优最大收益：" << maxProfit << endl; // 生成最优解 int x[3]; ks.GenerateAns(x); cout << "最优解（1选0不选）："; for (int i = 0; i < n; i++) cout << x[i] << " "; cout << endl; return 0; }