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

if(i<n){

node->b = p + (M - w)*a[i].p/a[i].w;

}else{

node -> b = p;

}

}

}

//用分支限界法实现0/1背包问题

int KnapSack4(int n,goods a[],int C, int X[])

{

int i, k = 0; // 堆中元素个数的计数器初始化为0

int v;

KNAPNODE *xnode, *ynode, *znode;

HEAP x, y, z, *heap;

heap = new HEAP[n*n]; // 分配堆的存储空间

for( i=0; i<n; i++){

a[i].sign=i; //记录物体的初始编号

}

sort(a,a+n,m); // 对物体按照价值重量比排序

xnode = new KNAPNODE; // 建立父亲结点

for( i=0; i<n; i++){ // 初始化结点

xnode->s1[i] = false;

}

xnode->k = xnode->w = xnode->p = 0;

while(xnode->k<n) {

ynode = new KNAPNODE; // 建立结点y

*ynode = *xnode; //结点x的数据复制到结点y

ynode->s1[ynode->k] = true; // 装入第k个物体

ynode->w += a[ynode->k].w; // 背包中物体重量累计

ynode->p += a[ynode->k].p; // 背包中物体价值累计

ynode->k ++; // 搜索深度++

bound(ynode, C, a, n); // 计算结点y的上界

y.b = ynode->b;

y.p = ynode;

insert(heap, y, k); //结点y按上界的值插入堆中

znode = new KNAPNODE; // 建立结点z

*znode = *xnode; //结点x的数据复制到结点z

znode->k++; // 搜索深度++

bound(znode, C, a, n); //计算节点z的上界

z.b = znode->b;

z.p = znode;

insert(heap, z, k); //结点z按上界的值插入堆中

delete xnode;

x = del_top(heap, k); //获得堆顶元素作为新的父亲结点