算法 背包問題

1、一、實驗?zāi)康呐c要求掌握回溯法、分支限界法的原理，并能夠按其原理編程實現(xiàn)解決0-1背包問題，以加深對回溯法、分支限界法的理解。1 要求分別用回溯法和分支限界法求解0-1背包問題；2 要求交互輸入背包容量，物品重量數(shù)組，物品價值數(shù)組；3 要求顯示結(jié)果。二、實驗方案在選擇裝入背包的物品時，對每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。三、實驗結(jié)果和數(shù)據(jù)處理 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) /判斷是否到達(dá)了葉子節(jié)點 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("物品個數(shù)：n=4&q

4、uot;); System.out.println("背包容量：c=7"); System.out.println("物品重量數(shù)組：w= 3,5,2,1"); System.out.println("物品價值數(shù)組：p= 9,10,7,4"); System.out.println("最優(yōu)值：="+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(); 運(yùn)行結(jié)果：2用優(yōu)先隊列式分支限界法解決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; /上界函數(shù)bound計算結(jié)點所相應(yīng)價值的上界 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將一個新的活結(jié)點插入到子集樹和

7、優(yōu)先隊列中 private static void addLiveNode(double up,double pp,double ww,int lev,BBnode par,boolean ch) /將一個新的活結(jié)點插入到子集樹和最大堆中 BBnode b=new BBnode(par,ch); HeapNode node =new HeapNode(b,up,pp,ww,lev); heap.put(node); private static double MaxKnapsack() /優(yōu)先隊列式分支限界法，返回最大價值，bestx返回最優(yōu)解 BBnode enode=null; int i

8、=1; double bestp=0;/當(dāng)前最優(yōu)值 double up=bound(1);/當(dāng)前上界 while(i!=n+1)/非葉子結(jié)點 /檢查當(dāng)前擴(kuò)展結(jié)點的左兒子子結(jié)點 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返回最優(yōu)解 c=cc; n=pp.length-1; /定義以單位重量價值排序的

10、物品數(shù)組 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;優(yōu)先隊列式分支限界法:"); System.out.println("物品個數(shù)：n=4"); System.out.println("背包容量：c=7"); System.out.println("物品重量數(shù)組：w= 3,5,2,1"); System.out.println("物品價值數(shù)組：p= 9,10,7,4"); System.out.println("最優(yōu)值：="+m); System.out.println("選中的物品是:"); for(int

13、i=1;i<=4;i+) System.out.print(xi+" "); /子空間中節(jié)點類型class BBnode BBnode parent;/父節(jié)點 boolean leftChild;/左兒子節(jié)點標(biāo)志 BBnode(BBnode par,boolean ch) parent=par; leftChild=ch; class HeapNode implements Comparable BBnode liveNode; / 活結(jié)點 double upperProfit; /結(jié)點的價值上界 double profit; /結(jié)點所相應(yīng)的價值 double wei

14、ght; /結(jié)點所相應(yīng)的重量 int level; / 活結(jié)點在子集樹中所處的層次號 /構(gòu)造方法 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); 運(yùn)行結(jié)果：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;/* 用隊列實現(xiàn)分支定界算法*/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