算法 0-1背包问题

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;/分别代表价值和重量 privat

2、e 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(in

3、t i) if(i>n) /判断是否到达了叶子节点 if(cp>bestp) for(int j=0;j<x.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&q

4、uot;); 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;i<x.length;i+) System.out.print(xi+" "

5、;); 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 d

6、ouble 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将一个新的活结点插入到子集树和

7、优先队列中 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

8、=1; double bestp=0;/当前最优值 double up=bound(1);/当前上界 while(i!=n+1)/非叶子结点 /检查当前扩展结点的左儿子子结点 double wt=cw+wi; if(wt<=c) if(cp+pi>bestp) 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.remov

9、eMax(); enode=node.liveNode; cw=node.weight; cp=fit; up=node.upperProfit; i=node.level; for(int j=n;j>0;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; /定义以单位重量价值排序的

10、物品数组 Element q=new Elementn; double ws=0.0; double ps=0.0; for(int i=0;i<n;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;i<n;i+) pi+1=ppqi.id; wi+1=wwqi.id; cw=0.0; cp=0.0; bestX = new intn+1; heap = new Max

11、Heap(n); double bestp = MaxKnapsack(); for(int j=0;j<n;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(&qu

12、ot;优先队列式分支限界法:"); 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

13、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 wei

14、ght; /结点所相应的重量 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;

15、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(d<xd)return -1; if(d=xd)return 0; return 1; public boolean equals(Object x) return d=(Ele

16、ment)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(nod

17、es); 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(j<m&&nodesj.upperProfit<nodesj+1.up

18、perProfit) +j; if(!(rc.upperProfit<nodesj.upperProfit) break; nodess = nodesj; s = j; nodess = rc; private static void heapSort(HeapNode nodes) for(int i=(nextPlace-1)/2;i>0;-i) heapAdjust(nodes,i,nextPlace-1); 运行结果：3用队列式分支限界法解决0-1背包问题：代码：#include<stdio.h>#include<stdlib.h>#define

19、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(

20、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( "

21、;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

22、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(i

23、nt 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 < n && m > 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 &a

24、mp;& 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

25、) return -1; enQueue_seq(q, x); while (!isEmptyQueue_seq(q)int step; DataType y; x = frontQueue_seq(q); deQueue_seq(q);if (x.max < min) continue; step = x.step + 1; if (step = n+1) continue; y.max = x.price + up(step, m - x.weight, n, p, w); if (y.max >= min)y.min = x.price + down(step, m-x.weight, n, p, w); y.price = x.price; y.weight = x.weight; y.step