1、算法 01背包问题教学教材算法 0-1背包问题一、实验目的与要求掌握回溯法、分支限界法的原理，并能够按其原理编程实现解决0-1背包问题，以加深对回溯法、分支限界法的理解。1 要求分别用回溯法和分支限界法求解0-1背包问题；2 要求交互输入背包容量，物品重量数组，物品价值数组；3 要求显示结果。二、实验方案在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。三、实验结果和数据处理 1用回溯法解决0-1背包问题：代码：import java.util.*;public class Knapsack private doubl
2、e p,w;/分别代表价值和重量 private int n; private double c,bestp,cp,cw; private int x; /记录可选的物品 private int cx; public Knapsack (double pp,double ww,double cc) this.p=pp;this.w=ww;this.n=pp.length-1; this.c=cc;this.cp=0;this.cw=0; this.bestp=0; x=new intww.length; cx=new intpp.length; void Knapsack() backtrac
3、k(0); void backtrack(int i) if(in) /判断是否到达了叶子节点 if(cpbestp) for(int j=0;jx.length;j+) xj=cxj; bestp=cp; return; if(cw+wi=c) /搜索右子树 cxi=1; cw+=wi; cp+=pi; backtrack(i+1); cw-=wi; cp-=pi; cxi=0; backtrack(i+1); /检查左子树 void printResult() System.out.println(回溯法); System.out.println(物品个数：n=4); System.out
4、.println(背包容量：c=7); System.out.println(物品重量数组：w= 3,5,2,1); System.out.println(物品价值数组：p= 9,10,7,4); System.out.println(最优值：=+bestp); System.out.println(选中的物品是:); for(int i=0;ix.length;i+) System.out.print(xi+ ); public static void main(String args) double p=9,10,7,4; double w=3,5,2,1; int maxweight=7
5、; Knapsack ks=new Knapsack(p,w,maxweight); ks.Knapsack(); /回溯搜索 ks.printResult(); 运行结果：2用优先队列式分支限界法解决0-1背包问题：代码：public class Knapsack static double c; static int n; static double w; static double p; static double cw; static double cp; static int bestX; static MaxHeap heap; /上界函数bound计算结点所相应价值的上界 pri
6、vate static double bound(int i) double cleft=c-cw; double b=cp; while(i=n&wi=cleft) cleft=cleft-wi; b=b+pi; i+; /装填剩余容量装满背包 if(i=n) b=b+pi/wi*cleft; return b; /addLiveNode将一个新的活结点插入到子集树和优先队列中 private static void addLiveNode(double up,double pp,double ww,int lev,BBnode par,boolean ch) /将一个新的活结点插入到子集树
7、和最大堆中 BBnode b=new BBnode(par,ch); HeapNode node =new HeapNode(b,up,pp,ww,lev); heap.put(node); private static double MaxKnapsack() /优先队列式分支限界法，返回最大价值，bestx返回最优解 BBnode enode=null; int i=1; double bestp=0;/当前最优值 double up=bound(1);/当前上界 while(i!=n+1)/非叶子结点 /检查当前扩展结点的左儿子子结点 double wt=cw+wi; if(wtbest
8、p) bestp=cp+pi; addLiveNode(up,cp+pi,cw+wi,i+1,enode,true); up=bound(i+1); if(up=bestp) addLiveNode(up,cp,cw,i+1,enode,false); HeapNode node =(HeapNode)heap.removeMax(); enode=node.liveNode; cw=node.weight; cp=node.profit; up=node.upperProfit; i=node.level; for(int j=n;j0;j-) bestXj=(enode.leftChild
9、)?1:0; enode=enode.parent; return cp; public static double Knapsack(double pp,double ww,double cc,int xx) /返回最大值，bestX返回最优解 c=cc; n=pp.length-1; /定义以单位重量价值排序的物品数组 Element q=new Elementn; double ws=0.0; double ps=0.0; for(int i=0;in;i+) qi=new Element(i+1,ppi+1/wwi+1); ps=ps+ppi+1; ws=ws+wwi+1; if(ws
10、=c) return ps; p=new doublen+1; w=new doublen+1; for(int i=0;in;i+) pi+1=ppqi.id; wi+1=wwqi.id; cw=0.0; cp=0.0; bestX = new intn+1; heap = new MaxHeap(n); double bestp = MaxKnapsack(); for(int j=0;jn;j+) xxqj.id=bestXj+1; return bestp; public static void main(String args) double w=new double5; w1=3;
11、w2=5;w3=2;w4=1; double p=new double5; p1=9;p2=10;p3=7;p4=4; double c=7; int x = new int5; double m = Knapsack(p,w,c,x); System.out.println(优先队列式分支限界法:); System.out.println(物品个数：n=4); System.out.println(背包容量：c=7); System.out.println(物品重量数组：w= 3,5,2,1); System.out.println(物品价值数组：p= 9,10,7,4); System.o
12、ut.println(最优值：=+m); System.out.println(选中的物品是:); for(int i=1;i=4;i+) System.out.print(xi+ ); /子空间中节点类型class BBnode BBnode parent;/父节点 boolean leftChild;/左儿子节点标志 BBnode(BBnode par,boolean ch) parent=par; leftChild=ch; class HeapNode implements Comparable BBnode liveNode; / 活结点 double upperProfit; /结
13、点的价值上界 double profit; /结点所相应的价值 double weight; /结点所相应的重量 int level; / 活结点在子集树中所处的层次号 /构造方法 public HeapNode(BBnode node, double up, double pp , double ww,int lev) liveNode = node; upperProfit = up; profit = pp; weight = ww; level = lev; public int compareTo(Object o) double xup = (HeapNode)o).upperPr
14、ofit; if(upperProfit xup) return -1; if(upperProfit = xup) return 0; else return 1; class Element implements Comparable int id; double d; public Element(int idd,double dd) id=idd; d=dd; public int compareTo(Object x) double xd=(Element)x).d; if(dxd)return -1; if(d=xd)return 0; return 1; public boole
15、an equals(Object x) return d=(Element)x).d; class MaxHeap static HeapNode nodes; static int nextPlace; static int maxNumber; public MaxHeap(int n) maxNumber = (int)Math.pow(double)2,(double)n); nextPlace = 1;/下一个存放位置 nodes = new HeapNodemaxNumber; public static void put(HeapNode node) nodesnextPlace
16、 = node; nextPlace+; heapSort(nodes); public static HeapNode removeMax() HeapNode tempNode = nodes1; nextPlace-; nodes1 = nodesnextPlace; heapSort(nodes); return tempNode; private static void heapAdjust(HeapNode nodes,int s,int m) HeapNode rc = nodess; for(int j=2*s;j=m;j*=2) if(jm&nodesj.upperProfi
17、tnodesj+1.upperProfit) +j; if(!(rc.upperProfit0;-i) heapAdjust(nodes,i,nextPlace-1); 运行结果：3用队列式分支限界法解决0-1背包问题：代码：#include#include#define MAXNUM 100struct node int step; double price; double weight; double max, min; unsigned long po;typedef struct node DataType;struct SeqQueue /* 顺序队列类型定义 */ int f, r
18、; DataType qMAXNUM;typedef struct SeqQueue *PSeqQueue; PSeqQueue createEmptyQueue_seq( void ) PSeqQueue paqu; paqu = (PSeqQueue)malloc(sizeof(struct SeqQueue); if (paqu = NULL) printf(Out of space! n); else paqu-f = paqu-r = 0; return paqu;int isEmptyQueue_seq( PSeqQueue paqu ) return paqu-f = paqu-
19、r;/* 在队列中插入一元素x */void enQueue_seq( PSeqQueue paqu, DataType x ) if(paqu-r + 1) % MAXNUM = paqu-f) printf( Full queue.n ); else paqu-qpaqu-r = x; paqu-r = (paqu-r + 1) % MAXNUM; /* 删除队列头元素 */void deQueue_seq( PSeqQueue paqu ) if( paqu-f = paqu-r ) printf( Empty Queue.n ); else paqu-f = (paqu-f + 1)
20、% MAXNUM;/* 对非空队列,求队列头部元素 */DataType frontQueue_seq( PSeqQueue paqu ) return (paqu-qpaqu-f);/* 物品按性价比从新排序*/void sort(int n, double p, double w) int i, j; for (i = 0; i n-1; i+) for (j = i; j n-1; j+) double a = pj/wj; double b = pj+1/wj+1; if (a b) double temp = pj; pj = pj+1; pj+1 = temp; temp = wj
21、; wj = wj+1; wj+1 = temp; /* 求最大可能值*/double up(int k, double m, int n, double p, double w) int i = k; double s = 0; while (i n & wi m) m -= wi; s += pi; i+; if (i 0) s += pi * m / wi; i+; return s;/* 求最小可能值*/double down(int k, double m, int n, double p, double w) int i = k; double s = 0; while (i n
22、& wi = m) m -= wi; s += pi; i+; return s;/* 用队列实现分支定界算法*/double solve(double m, int n, double p, double w, unsigned long* po) double min; PSeqQueue q = createEmptyQueue_seq(); DataType x = 0,0,0,0,0,0; sort(n, p, w); x.max = up(0, m, n, p, w); x.min = min = down(0, m, n, p, w); if (min = 0) return -
23、1; enQueue_seq(q, x); while (!isEmptyQueue_seq(q) int step; DataType y; x = frontQueue_seq(q); deQueue_seq(q); if (x.max = min) y.min = x.price + down(step, m-x.weight, n, p, w); y.price = x.price; y.weight = x.weight; y.step = step; y.po = x.po = min) min = y.min; if (step = n) *po = y.po; enQueue_
24、seq(q, y); if (x.weight+wstep-1= min) y.min = x.price + pstep-1 + down(step, m-x.weight-wstep-1, n, p, w); y.price = x.price + pstep-1; y.weight = x.weight + wstep-1; y.step = step; y.po = (x.po = min) min = y.min; if (step = n) *po = y.po; enQueue_seq(q, y); return min;#define n 4double m = 7;double pn = 9, 10, 7, 4;double wn = 3, 5, 1, 2;int main() int i; double d; unsigned long po; d = solve(m, n, p, w, &po); if (d = -1) printf(No solution!n); else for (i = 0; i n; i+) printf(x%d 为 %dn, i + 1, (po & (1(n-i-1) != 0); printf(最优值是：%fn, d); getchar(); return 0;运行结果：
