01背包分支要点Word格式.docx

01背包分支要点Word格式.docx

《01背包分支要点Word格式.docx》由会员分享，可在线阅读，更多相关《01背包分支要点Word格式.docx（13页珍藏版）》请在冰点文库上搜索。

{C}—>

{F，G}—>

{G，L，M}—>

{G，M}—>

{G}—>

{N，O}—>

{O}—>

{}

//0-1背包问题分支限界法求解

#include"

stdafx.h"

MaxHeap.h"

#include<

iostream>

usingnamespacestd;

classObject

{

template<

classTypew,classTypep>

friendTypepKnapsack（Typepp[],Typeww[],Typewc,intn,intbestx[]）;

public:

intoperator<

=（Objecta）const

{

returnd>

=a.d;

}

private:

intID;

floatd;

//单位重量价值

};

template<

classKnap;

classbbnode

friendKnap<

int,int>

;

bbnode*parent;

//指向父节点的指针

boolLChild;

//左儿子节点标识

classHeapNode

Typew,Typep>

operatorTypep（）const

returnuprofit;

Typepuprofit,//节点的价值上界

profit;

//节点所相应的价值

Typewweight;

//节点所相应的重量

intlevel;

//活节点在子集树中所处的层序号

bbnode*ptr;

//指向活节点在子集中相应节点的指针

classKnap

TypepMaxKnapsack（）;

MaxHeap<

HeapNode<

Typep,Typew>

>

*H;

TypepBound（inti）;

voidAddLiveNode（Typepup,Typepcp,Typewcw,boolch,intlev）;

bbnode*E;

//指向扩展节点的指针

Typewc;

//背包容量

intn;

//物品数

Typew*w;

//物品重量数组

Typep*p;

//物品价值数组

Typewcw;

//当前重量

Typepcp;

//当前价值

int*bestx;

//最优解

template<

classType>

inlinevoidSwap（Type&

a,Type&

b）;

voidBubbleSort（Typea[],intn）;

intmain（）

intn=3;

//物品数

intc=30;

//背包容量

intp[]={0,45,25,25};

//物品价值下标从1开始

intw[]={0,16,15,15};

//物品重量下标从1开始

intbestx[4];

//最优解

cout<

<

"

背包容量为：

c<

endl;

物品重量和价值分别为：

for（inti=1;

i<

=n;

i++）

（"

w[i]<

"

p[i]<

）"

背包能装下的最大价值为：

Knapsack（p,w,c,n,bestx）<

此背包问题最优解为:

bestx[i]<

"

return0;

}

TypepKnap<

:

Bound（inti）//计算节点所相应价值的上界

Typewcleft=c-cw;

//剩余容量高

Typepb=cp;

//价值上界

//以物品单位重量价值递减序装填剩余容量

while（i<

=n&

&

w[i]<

=cleft）

cleft-=w[i];

b+=p[i];

i++;

//装填剩余容量装满背包

if（i<

=n）

b+=p[i]/w[i]*cleft;

returnb;

//将一个活节点插入到子集树和优先队列中

voidKnap<

AddLiveNode（Typepup,Typepcp,Typewcw,boolch,intlev）

bbnode*b=newbbnode;

b->

parent=E;

LChild=ch;

HeapNode<

N;

N.uprofit=up;

N.profit=cp;

N.weight=cw;

N.level=lev;

N.ptr=b;

H->

Insert（N）;

//优先队列式分支限界法，返回最大价值，bestx返回最优解

MaxKnapsack（）

H=newMaxHeap<

（1000）;

//为bestx分配存储空间

bestx=newint[n+1];

//初始化

inti=1;

E=0;

cw=cp=0;

Typepbestp=0;

//当前最优值

Typepup=Bound

（1）;

//搜索子集空间树

while（i!

=n+1）

//检查当前扩展节点的左儿子节点

Typewwt=cw+w[i];

if（wt<

=c）//左儿子节点为可行节点

if（cp+p[i]>

bestp）

bestp=cp+p[i];

AddLiveNode（up,cp+p[i],cw+w[i],true,i+1）;

up=Bound（i+1）;

//检查当前扩展节点的右儿子节点

if（up>

=bestp）//右子树可能含有最优解

AddLiveNode（up,cp,cw,false,i+1）;

//取下一扩展节点

DeleteMax（N）;

E=N.ptr;

cw=N.weight;

cp=N.profit;

up=N.uprofit;

i=N.level;

//构造当前最优解

for（intj=n;

j>

0;

j--）

bestx[j]=E->

LChild;

E=E->

parent;

returncp;

//返回最大价值，bestx返回最优解

TypepKnapsack（Typepp[],Typeww[],Typewc,intn,intbestx[]）

TypewW=0;

//装包物品重量

TypepP=0;

//装包物品价值

//定义依单位重量价值排序的物品数组

Object*Q=newObject[n];

//单位重量价值数组

Q[i-1].ID=i;

Q[i-1].d=1.0*p[i]/w[i];

P+=p[i];

W+=w[i];

if（W<

=c）

returnP;

//所有物品装包

//依单位价值重量排序

BubbleSort（Q,n）;

//创建类Knap的数据成员

Knap<

K;

K.p=newTypep[n+1];

K.w=newTypew[n+1];

K.p[i]=p[Q[i-1].ID];

K.w[i]=w[Q[i-1].ID];

K.cp=0;

K.cw=0;

K.c=c;

K.n=n;

//调用MaxKnapsack求问题的最优解

Typepbestp=K.MaxKnapsack（）;

for（intj=1;

j<

j++）

bestx[Q[j-1].ID]=K.bestx[j];

deleteQ;

delete[]K.w;

delete[]K.p;

delete[]K.bestx;

returnbestp;

voidBubbleSort（Typea[],intn）

//记录一次遍历中是否有元素的交换

boolexchange;

for（inti=0;

n-1;

i++）

exchange=false;

for（intj=i+1;

=n-1;

if（a[j]<

=a[j-1]）

Swap（a[j],a[j-1]）;

exchange=true;

//如果这次遍历没有元素的交换,那么排序结束

if（false==exchange）

break;

b）

Typetemp=a;

a=b;

b=temp;

}