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

算法实验-优先队列式分⽀限界法解01背包问题实验原理分⽀限界法采⽤的是⼴度优先搜索，⽽优先队列采⽤的是队列⾥最优的出队，这⾥可以使⽤最⼤堆来实现活接垫优先队列，最⼤堆以活节点的界值作为优先级。实验步骤左⼦树的解的上界与⽗节点相同，不⽤计算。右⼦树的解的界值是：将剩余物品以其单位重量价值排序，然后依次装⼊物品，直到装不下时，再装⼊物品的⼀部分来装满背包，即采⽤贪⼼算法算出最⼤值，由此得到右⼦树中解的上界（虽然不是⼀个可⾏解，但可以作为最优解的上界）。关键代码double bound(int i) { double cleft = c - cw; double b = cp; while (i <= n && w[i] <= cleft) { cleft = cleft - w[i]; b = b + p[i]; i++; } //

装填剩余容量装满背包 if (i <= n) b = b + p[i] / w[i] * cleft; return b;}// addLiveNode将⼀个新的活结点插⼊到⼦集树和优先队列中void addLiveNode(double up, double pp, double ww, int lev, BBnode* par, bool ch) { //

将⼀个新的活结点插⼊到⼦集树和最⼤堆中 BBnode* b = new BBnode(par, ch); HeapNode node = HeapNode(b, up, pp, ww, lev); heap->put(node);}double MaxKnapsack(){ //

优先队列式分⽀限界法，返回最⼤价值，bestx返回最优解 BBnode* enode = new BBnode(); int i = 1; double bestp = 0; //

当前最优值 double up = bound(1); //

当前上界 while (i != n + 1) {//

⾮叶⼦结点 //

检查当前扩展结点的左⼉⼦⼦结点 double wt = cw + w[i]; if (wt <= c) { if (cp + p[i] > bestp) bestp = cp + p[i]; addLiveNode(up, cp + p[i], cw + w[i], i + 1, enode, true); } up = bound(i + 1); if (up >= bestp) addLiveNode(up, cp, cw, i + 1, enode, false); HeapNode node = heap->removeMax(); enode = de; cw = ; cp = ; up = rofit; i = ; } for (int j = n; j > 0; j--) { bestX[j] = (enode->leftChild) ? 1 : 0; enode = enode->parent; enode = enode->parent; } return cp;}double knapsack(double* pp, double* ww, double cc, int* xx) { //

返回最⼤值，bestX返回最优解 c = cc; // n = sizeof(pp) / sizeof(double); //

定义以单位重量价值排序的物品数组 Element* q = new Element[n]; double ws = 0.0; double ps = 0.0; for (int i = 0; i < n; i++) { q[i] = Element(i + 1, pp[i + 1] / ww[i + 1]); ps = ps + pp[i + 1]; ws = ws + ww[i + 1]; } if (ws <= c) { return ps; } p = new double[n + 1]; w = new double[n + 1]; for (int i = 0; i < n; i++){ p[i + 1] = pp[q[i].id]; w[i + 1] = ww[q[i].id]; } cw = 0.0; cp = 0.0; bestX = new int[n + 1]; heap = new MaxHeap(n); double bestp = MaxKnapsack(); for (int j = 0; j < n; j++) xx[q[j].id] = bestX[j + 1]; return bestp;}

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

算法实验-优先队列式分⽀限界法解01背包问题实验原理分⽀限界法采⽤的是⼴度优先搜索，⽽优先队列采⽤的是队列⾥最优的出队，这⾥可以使⽤最⼤堆来实现活接垫优先队列，最⼤堆以活节点的界值作为优先级。实验步骤左⼦树的解的上界与⽗节点相同，不⽤计算。右⼦树的解的界值是：将剩余物品以其单位重量价值排序，然后依次装⼊物品，直到装不下时，再装⼊物品的⼀部分来装满背包，即采⽤贪⼼算法算出最⼤值，由此得到右⼦树中解的上界（虽然不是⼀个可⾏解，但可以作为最优解的上界）。关键代码double bound(int i) { double cleft = c - cw; double b = cp; while (i <= n && w[i] <= cleft) { cleft = cleft - w[i]; b = b + p[i]; i++; } //

装填剩余容量装满背包 if (i <= n) b = b + p[i] / w[i] * cleft; return b;}// addLiveNode将⼀个新的活结点插⼊到⼦集树和优先队列中void addLiveNode(double up, double pp, double ww, int lev, BBnode* par, bool ch) { //

将⼀个新的活结点插⼊到⼦集树和最⼤堆中 BBnode* b = new BBnode(par, ch); HeapNode node = HeapNode(b, up, pp, ww, lev); heap->put(node);}double MaxKnapsack(){ //

优先队列式分⽀限界法，返回最⼤价值，bestx返回最优解 BBnode* enode = new BBnode(); int i = 1; double bestp = 0; //

当前最优值 double up = bound(1); //

当前上界 while (i != n + 1) {//

⾮叶⼦结点 //

检查当前扩展结点的左⼉⼦⼦结点 double wt = cw + w[i]; if (wt <= c) { if (cp + p[i] > bestp) bestp = cp + p[i]; addLiveNode(up, cp + p[i], cw + w[i], i + 1, enode, true); } up = bound(i + 1); if (up >= bestp) addLiveNode(up, cp, cw, i + 1, enode, false); HeapNode node = heap->removeMax(); enode = de; cw = ; cp = ; up = rofit; i = ; } for (int j = n; j > 0; j--) { bestX[j] = (enode->leftChild) ? 1 : 0; enode = enode->parent; enode = enode->parent; } return cp;}double knapsack(double* pp, double* ww, double cc, int* xx) { //

返回最⼤值，bestX返回最优解 c = cc; // n = sizeof(pp) / sizeof(double); //

定义以单位重量价值排序的物品数组 Element* q = new Element[n]; double ws = 0.0; double ps = 0.0; for (int i = 0; i < n; i++) { q[i] = Element(i + 1, pp[i + 1] / ww[i + 1]); ps = ps + pp[i + 1]; ws = ws + ww[i + 1]; } if (ws <= c) { return ps; } p = new double[n + 1]; w = new double[n + 1]; for (int i = 0; i < n; i++){ p[i + 1] = pp[q[i].id]; w[i + 1] = ww[q[i].id]; } cw = 0.0; cp = 0.0; bestX = new int[n + 1]; heap = new MaxHeap(n); double bestp = MaxKnapsack(); for (int j = 0; j < n; j++) xx[q[j].id] = bestX[j + 1]; return bestp;}