蛮力法、动态规划法、回溯法和分支限界法求解(9)

}

}

//往堆中插入结点

void insert(HEAP H[], HEAP x, int &n)

{

n++;

H[n] = x;

mov_up(H,n);

}

//删除堆中结点

void del(HEAP H[], int &n, int i)

{

HEAP x, y;

x = H[i]; y = H[n];

n --;

if(i<=n){

H[i] = y;

if(y.b>=x.b){

mov_up(H,i);

}else{

mov_down(H, n, i);

}

}

}

//获得堆顶元素并删除

HEAP del_top(HEAP H[], int &n)

{

HEAP x = H[1];

del(H, n, 1);

return x;

}

//计算分支节点的上界

void bound( KNAPNODE* node, int M, goods a[], int n)

{

int i = node->k;

float w = node->w;

float p = node->p;

if(node->w>M){ // 物体重量超过背包载重量

node->b = 0; // 上界置为0

}else{

while((w+a[i].w<=M)&&(i<n)){

w += a[i].w; // 计算背包已装入载重

p += a[i++].p; // 计算背包已装入价值

}