2023年8月1日发(作者：)

算法---分⽀限定01背包--蚁群算法⽤蚁群算法解决01背包问题。我本以为就是完全的蛮⼒法，但百度后觉得应该是这个（4）分⽀限界-优先队列（STL）

// # 分⽀限界优先队列法// 队列中的节点类型struct NodeType{// 分⽀限界节点 int no; // 节点编号 int i; // 当前节点在搜索空间的层次 int w; // 当前节点的总重量 int v; // 当前节点的总价值 int x[MAXN]; // 当前节点包含的解向量 double ub; // 上界

bool operator<(const NodeType& node) const {// 优先队列按此⽅式排序 return ub < ; // ub越⼤越优先出队 }};/* 主⼲ * ->初始化根节点 * ->计算根节点上界及进队 * ->循环遍历队列，条件为⾮空：出⼀个节点, 计算左孩⼦节点剪枝条件，满⾜的左孩⼦计算上界及进队； 计算右孩⼦节点上界，符合上界条件的右孩⼦进队； （根据容量剪去左孩⼦，根据上界条件剪去右孩⼦） **/void bfs();

// 进队----不是叶⼦节点就直接进队，是叶⼦节点则判断是否更优解，是的话则更新最优解void EnQueue(NodeType e,priority_queue &qu);// 计算边界 就是根据剩余容量的⼤⼩，计算剩下全部物品装⼊的价值和装⼊部分物品的价值// （部分物品按照单位容量内价值⾼低的顺序装⼊---这有点贪⼼的思想了）void bound(NodeType &e);// !# 分⽀限界优先队列法

2023年8月1日发(作者：)

算法---分⽀限定01背包--蚁群算法⽤蚁群算法解决01背包问题。我本以为就是完全的蛮⼒法，但百度后觉得应该是这个（4）分⽀限界-优先队列（STL）

// # 分⽀限界优先队列法// 队列中的节点类型struct NodeType{// 分⽀限界节点 int no; // 节点编号 int i; // 当前节点在搜索空间的层次 int w; // 当前节点的总重量 int v; // 当前节点的总价值 int x[MAXN]; // 当前节点包含的解向量 double ub; // 上界

bool operator<(const NodeType& node) const {// 优先队列按此⽅式排序 return ub < ; // ub越⼤越优先出队 }};/* 主⼲ * ->初始化根节点 * ->计算根节点上界及进队 * ->循环遍历队列，条件为⾮空：出⼀个节点, 计算左孩⼦节点剪枝条件，满⾜的左孩⼦计算上界及进队； 计算右孩⼦节点上界，符合上界条件的右孩⼦进队； （根据容量剪去左孩⼦，根据上界条件剪去右孩⼦） **/void bfs();

// 进队----不是叶⼦节点就直接进队，是叶⼦节点则判断是否更优解，是的话则更新最优解void EnQueue(NodeType e,priority_queue &qu);// 计算边界 就是根据剩余容量的⼤⼩，计算剩下全部物品装⼊的价值和装⼊部分物品的价值// （部分物品按照单位容量内价值⾼低的顺序装⼊---这有点贪⼼的思想了）void bound(NodeType &e);// !# 分⽀限界优先队列法