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

int p; //物体价值

};

struct HEAP //堆元素结构体

{

KNAPNODE *p;//结点数据

int b; //所指结点的上界

};

//交换两个堆元素

void swap(HEAP &a, HEAP &b)

{

HEAP temp = a;

a = b;

b = temp;

}

//堆中元素上移

void mov_up(HEAP H[], int i)

{

bool done = false;

if(i!=1){

while(!done && i!=1){

if(H[i].b>H[i/2].b){

swap(H[i], H[i/2]);

}else{

done = true;

}

i = i/2;

}

}

}

//堆中元素下移

void mov_down(HEAP H[], int n, int i)

{

bool done = false;

if((2*i)<=n){

while(!done && ((i = 2*i) <= n)){

if(i+1<=n && H[i+1].b > H[i].b){

i++;

}

if(H[i/2].b<H[i].b){

swap(H[i/2], H[i]);

}else{

done = true;

}

}