算法 0-1背包问题

一、实验目的与要求掌握回溯法、分支限界法的原理，并能够按其原理编程实现解决0-1背包问题，以加深对回溯法、分支限界法的理解。1 要求分别用回溯法和分支限界法求解0-1背包问题；2 要求交互输入背包容量，物品重量数组，物品价值数组；3 要求显示结果。二、实验方案在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。三、实验结果和数据处理 1用回溯法解决0-1背包问题：代码：import java.util.*;public class Knapsack private double 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() backtrack(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.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; 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计算结点所相应价值的上界 private 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) /将一个新的活结点插入到子集树和最大堆中 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(wtbestp) 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=fit; up=node.upperProfit; i=node.level; for(int j=n;j0;j-) bestXj=(enode.leftChild)?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=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;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.out.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; /结点的价值上界 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).upperProfit; 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 boolean 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 = 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.upperProfitnodesj+1.upperProfit) +j; if(!(rc.upperProfit0;-i) heapAdjust(nodes,i,nextPlace-1); 运行结果：3用队列式分支限界法解决0-1背包问题：代码：#include#include#define MAXNUM 100struct nodeint step;double price; double weight; double max, min; unsigned long po;typedef struct node DataType;struct SeqQueue /* 顺序队列类型定义 */int f, r;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-r;/* 在队列中插入一元素x */void enQueue_seq( PSeqQueue paqu, DataType x ) if(paqu-r + 1) % MAXNUM = paqu-f)printf( Full queue.n );elsepaqu-qpaqu-r = x; paqu-r = (paqu-r + 1) % MAXNUM;/* 删除队列头元素 */void deQueue_seq( PSeqQueue paqu )if( paqu-f = paqu-r )printf( Empty Queue.n );elsepaqu-f = (paqu-f + 1) % 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; 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 & 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 -1; enQueue_seq(q, x); while (!isEmptyQueue_seq(q)int step; DataType y; x = frontQueue_seq(q); deQueue_seq(q);if (x.max =