分枝限界法求解 0/1背包问题

#includeiostream #includecmath using namespace std; // 全局常量定义 // 极小值用于边界比较 const float epsilon 1e-6f; // 模板零值适配不同数值类型 templateclass 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 等 */ templateclass 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 队列元素类型 */ templateclass 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只装完整物品求保守收益 */ templateclass T void KnapsackT::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 分枝限界主算法实现 templateclass T T KnapsackT::LCBB() { Node* child; // 孩子结点指针 Node* E; // 当前扩展结点 T LBB, UBB, L; // 下界、上界、当前最优值 ans NULL; // 最优解结点初始空 // 初始化优先队列 prioQueuepqNodeT pq(mSize); // 建立根结点无父亲不是左孩子 root new Node(NULL, false); // 计算根结点上下界 LUBound(0, m, 0, LBB, UBB); // 根结点入队 pqNodeT 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); // 构造新结点并入队 pqNodeT 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); pqNodeT 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; } // 构造函数实现 templateclass T KnapsackT::Knapsack(T* prof, float* wei, float mm, int len) { n len; p prof; w wei; m mm; ans root NULL; } // 生成最优解数组实现 templateclass T void KnapsackT::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: p60, w10 → 6 // 物品 1: p100, w20 →5 // 物品 2: p120, w30 →4 int p[] {60, 100, 120}; float w[] {10, 20, 30}; float m 50; int n 3; // 创建背包对象 Knapsackint 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; }