算法0-1背包问题

1、一、实验目的与要求掌握回溯法、分支限界法的原理，并能够按其原理编程实现解决0-1背包问题，以 加深对回溯法.分支限界法的理解。1. 要求分别用回溯法和分支限界法求解0-1背包问题；2. 要求交互输入背包容呈，物品重量数组，物品价值数组；3. 要求显不结果。二、实验方案在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物 品i装入背包多次，也不能只装入部分的物品i。三、实验结果和数据处理1.用回溯法解决0-1背包问题：代码；import ;public class Knapsack privatedoubletP,w;回溯法：物品个数: n=4背包客愛:c=7物品重

2、屋数组咗 初品价值数组P二忧值=20. 0 选中的物品足：10 11战功生战他5, 2川10, 7,4d；wi+l=wqi id;cw=;cp=；bestX = new intn+l;heap = new MaxHeap(n);double bestp = MaxKnapsackO ； for (int j=O;jn;j+)xxqj id=bestXj+l;return bestp;public static void main(String args) double w=new double5;wl=3;w2=5;w3=2;w4=l;double p=new double5; pl=9;p2

3、=10;p3=7;p4=4;double c=7;int x = new int5:double m = Knapsack (p, w, c, x);优先队列式分支限界法:)； 物品个数：n=4*);背包容量：c=7);物品重量数组：w= 3t 5,2,1);物品价值数组：P= 9,10,7,4);瘁最优值：二”+m)；选中的物品是:)；for (int i=l;i=4;i+)0;pperProfit;if (upperProfit xup) return -1;if (upperProfit = xup) return 0;else return 1;class Element implem

4、ents Comparableint 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 MaxHeapstatic HeapNode nodes;static int nextPlace;static int

5、 maxNumber;public MaxHeap(int n)maxNumber = (int) (double)2, (double)n);nextPlace = 1;pperProf itnodesj+1uppcrProfit)+j；if (!0;i)heapAdjust(nodes, i, nextPlace-1);运行结果:输出Knapsack (rim)A FE代先臥列戎分支限界迭：物品个数n=4背包春量c=7物昂笙量数组： 他5, 2,1物品愉值数组丄P= % 10, 7,4If-ffi.1 =20. 0握中的物品呈：10 11战功生卓（总时间：0秋3.用队列式分支限界法解决0-

6、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 =

7、 (PSeqQueue)malloc(sizeof(struct SeqQueue); if (paqu = NULL)printf COut of space! n);elsepaqu-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 queuen);e

8、lsepaqu-qpaqu-r = x; paqu-r = (paqu-r + 1) % MAXNUM;/*删除队列头元素/void deQueue.seqC PSeqQueue paqu )if( paqu-f = paqu-r ) printf( Empty Queue. Xn* );elsepaqu-f = (paqu-f + 1) % MAXNUM;/*对非空队列，求队列头部元素*/DataType frontQueue_seq( PSeqQueue paqu ) return (paqu-qpaqu-f);/*物品按性价比从新排序权void sort(int n, double p,

9、 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+l/wj+l; if (a double m int n double p, double w)int i = k;double s = 0;while (i n & wi m)m y wi;S += pi；i+；if (i 0)s += pi * m / wi;i+；return s;/*求最小可能值*/double down(int k, double m, int n, double p, doub

10、le w)int i = k;double s = 0;while (i n & wi w)；=min = down (0, m, n, p, w);if (min = 0) return -1; enQueuc.seq(q, x);while (!isEmptyQueue_seq(q)int step;DataType y;x = frontQueue_seq(q); deQueue_seq(q);if = min)=+ down (step, , n, p, w);=step;= 1;if = min)min =;if (step = n) *po =;enQueujseq (q, y);

11、if +wstep-l= min) =+ pstep-l + down (step, step-1, n, p, =+ pstep-l; =+ wstep-l;=step;= 1) + 1;if = min)min =;if (step = n) *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 mainOint i;double d;unsigned long po;d = solve (m, n p, w, &po);if (d = -1)printfCNo solution!Xn