分别用回溯法和分支限界法求解0-1背包问题

0-1背包动态规划解决问题一、问题描述：有n个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？二、总体思路：根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成）找出01背包问题的最优解以及解组成，然后编写代码实现。

原理：动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。

但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。

过程：a) 把背包问题抽象化（X1，X2，…，Xn，其中 Xi 取0或1，表示第i 个物品选或不选），V i表示第i 个物品的价值，W i表示第i 个物品的体积（重量）；b) 建立模型，即求max(V1X1+V2X2+…+VnXn)；c) 约束条件，W1X1+W2X2+…+WnXn<capacity；d) 定义V(i,j)：当前背包容量j，前i 个物品最佳组合对应的价值；e) 最优性原理是动态规划的基础，最优性原理是指“多阶段决策过程的最优决策序列具有这样的性质：不论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，其后各阶段的决策序列必须构成最优策略”。

判断该问题是否满足最优性原理，采用反证法证明：假设(X1，X2，…，Xn)是01背包问题的最优解，则有(X2，X3，…，Xn)是其子问题的最优解，假设(Y2，Y3，…，Yn)是上述问题的子问题最优解，则理应有(V2Y2+V3Y3+…+V n Yn)+V1X1 > (V2X2+V3X3+…+VnXn)+V1X1；而(V2X2+V3X3+…+VnXn)+V1X1=(V1X1+V2X2+…+VnXn)，则有(V2Y2+V3Y3+…+VnYn)+V1X1 > (V1X1+V2X2+…+VnXn)；该式子说明(X1，Y2，Y3，…，Yn)才是该01背包问题的最优解，这与最开始的假设(X1，X2，…，Xn)是01背包问题的最优解相矛盾，故01背包问题满足最优性原理；f) 寻找递推关系式，面对当前商品有两种可能性：第一，包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)；第二，还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i) ｝其中V(i-1,j)表示不装，V(i-1,j-w(i))+v(i) 表示装了第i个商品，背包容量减少w(i)但价值增加了v(i)；由此可以得出递推关系式：1) j<w(i) V(i,j)=V(i-1,j)2) j>=w(i) V(i,j)=max｛ V(i-1,j)，V(i-1,j-w(i))+v(i) ｝number＝4，capacity＝7四、构造最优解：最优解的构造可根据C列的数据来构造最优解，构造时从第一个物品开始。

0-1背包问题计科1班朱润华 32方法1：回溯法一、回溯法描述：用回溯法解问题时，应明确定义问题的解空间。

问题的解空间至少包含问题的一个（最优）解。

对于0-1背包问题，解空间由长度为n的0-1向量组成。

该解空间包含对变量的所有0-1赋值。

例如n=3时，解空间为：｛（0，0，0），（0，1，0），（0，0，1），（1，0，0），（0，1，1），（1，0，1），（1，1，0），（1，1，1）｝然后可将解空间组织成树或图的形式，0-1背包则可用完全二叉树表示其解空间给定n种物品和一背包。

物品i的重量是wi，其价值为vi，背包的容量为C。

问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,), xi∈{0,1}, ∑ wi xi≤c,且∑ vi xi达最大.即一个特殊的整数规划问题。

二、回溯法步骤思想描述：0-1背包问题是子集选取问题。

0-1 背包问题的解空间可以用子集树表示。

在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索就进入左子树。

当右子树中有可能含有最优解时，才进入右子树搜索。

否则，将右子树剪去。

设r是当前剩余物品价值总和，cp是当前价值；bestp是当前最优价值。

当cp+r<=bestp时，可剪去右子树。

计算右子树上界的更好的方法是将剩余物品依次按其单位价值排序，然后依次装入物品，直至装不下时，再装入物品一部分而装满背包。

例如：对于0-1背包问题的一个实例，n=4,c=7,p=[9,10,7,4],w=[3,5,2,1]。

这4个物品的单位重量价值分别为[3,2,3,5,4]。

以物品单位重量价值的递减序装入物品。

先装入物品4，然后装入物品3和1.装入这3个物品后，剩余的背包容量为1，只能装的物品2。

由此得一个解为[1,,1,1]，其相应价值为22。

尽管这不是一个可行解，但可以证明其价值是最优值的上界。

问题描述0/1 背包问题 :现有 n 种物品，对 1<=i<=n ，已知第 i 种物品的重量为正整数 W i ，价值为正整数 V i ， 背包能承受的最大载重量为正整数 W ，现要求找出这 n 种物品的一个子集，使得子集中物 品的总重量不超过 W 且总价值尽量大。

(注意：这里对每种物品或者全取或者一点都不取， 不允许只取一部分)算法分析根据问题描述，可以将其转化为如下的约束条件和目标函数：nw i x i W i 1 i i(1)x i { 0,1}( 1 i n)nmax v i x i (2) i1于是，问题就归结为寻找一个满足约束条件( 1 )，并使目标函数式( 2 )达到最大的 解向量 X (x 1, x 2 ,x 3, ........... , x n ) 。

首先说明一下 0-1 背包问题拥有最优解。

假设 (x 1,x 2,x 3, ........ ,x n ) 是所给的问题的一个最优解， 则(x 2,x 3, ............... ,x n )是下面问题的n n n个问 题 的 一 个 最 优解 ， 则v i y iv i x i ， 且 w 1x 1w i y i W 。

因此 ，i 2 i 2 i 2一个最优解：w i x i Wi2w 1x 1nmax v i x i 。

如果不是的话，设(y 2,y 3, , y n ) 是这x i {0,1}( 2 i n)i2n n nv1x1 v i y i v1x1 v i x i v i x i ，这说明(x1,y2,y3, ............. ,y n) 是所给的0-1 背包问i 2 i 2 i 1题比( x1 , x 2 , x3 , ... , x n ) 更优的解，从而与假设矛盾。

穷举法：用穷举法解决0-1 背包问题，需要考虑给定n 个物品集合的所有子集，找出所有可能的子集(总重量不超过背包重量的子集) ，计算每个子集的总重量，然后在他们中找到价值最大的子集。

回溯法解决0-1背包问题问题描述： 有n件物品和⼀个容量为c的背包。

第i件物品的价值是v[i]，重量是w[i]。

求解将哪些物品装⼊背包可使价值总和最⼤。

所谓01背包，表⽰每⼀个物品只有⼀个，要么装⼊，要么不装⼊。

回溯法： 01背包属于找最优解问题，⽤回溯法需要构造解的⼦集树。

在搜索状态空间树时，只要左⼦节点是可⼀个可⾏结点，搜索就进⼊其左⼦树。

对于右⼦树时，先计算上界函数，以判断是否将其减去，剪枝啦啦！上界函数bound():当前价值cw+剩余容量可容纳的最⼤价值<=当前最优价值bestp。

为了更好地计算和运⽤上界函数剪枝，选择先将物品按照其单位重量价值从⼤到⼩排序，此后就按照顺序考虑各个物品。

#include <stdio.h>#include <conio.h>int n;//物品数量double c;//背包容量double v[100];//各个物品的价值double w[100];//各个物品的重量double cw = 0.0;//当前背包重量double cp = 0.0;//当前背包中物品价值double bestp = 0.0;//当前最优价值double perp[100];//单位物品价值排序后int order[100];//物品编号int put[100];//设置是否装⼊//按单位价值排序void knapsack(){int i,j;int temporder = 0;double temp = 0.0;for(i=1;i<=n;i++)perp[i]=v[i]/w[i];for(i=1;i<=n-1;i++){for(j=i+1;j<=n;j++)if(perp[i]<perp[j])//冒泡排序perp[],order[],sortv[],sortw[]{temp = perp[i];perp[i]=perp[i];perp[j]=temp;temporder=order[i];order[i]=order[j];order[j]=temporder;temp = v[i];v[i]=v[j];v[j]=temp;temp=w[i];w[i]=w[j];w[j]=temp;}}}//回溯函数void backtrack(int i){double bound(int i);if(i>n){bestp = cp;return;}if(cw+w[i]<=c){cw+=w[i];cp+=v[i];put[i]=1;backtrack(i+1);cw-=w[i];cp-=v[i];}if(bound(i+1)>bestp)//符合条件搜索右⼦数backtrack(i+1);}//计算上界函数double bound(int i){double leftw= c-cw;double b = cp;while(i<=n&&w[i]<=leftw){leftw-=w[i];b+=v[i];i++;}if(i<=n)b+=v[i]/w[i]*leftw;return b;}int main(){int i;printf("请输⼊物品的数量和容量：");scanf("%d %lf",&n,&c);printf("请输⼊物品的重量和价值：");for(i=1;i<=n;i++){printf("第%d个物品的重量：",i);scanf("%lf",&w[i]);printf("价值是：");scanf("%lf",&v[i]);order[i]=i;}knapsack();backtrack(1);printf("最有价值为：%lf\n",bestp);printf("需要装⼊的物品编号是：");for(i=1;i<=n;i++){if(put[i]==1)printf("%d ",order[i]);}return 0;}时间复杂度分析： 上界函数bound()需要O(n)时间，在最坏的情况下有O(2^n)个右⼦结点需要计算上界，回溯算法backtrack需要的计算时间为O(n2^n)。

算法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 int[ww.length];cx=new int[pp.length];}void Knapsack(){backtrack(0);}void backtrack(int i){if(i>n){ //判断是否到达了叶子节点if(cp>bestp){for(int j=0;j<x.length;j++)x[j]=cx[j];bestp=cp;}return;}if(cw+w[i]<=c){//搜索右子树cx[i]=1;cw+=w[i];cp+=p[i];backtrack(i+1);cw-=w[i];cp-=p[i];}cx[i]=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;i<x.length;i++){System.out.print(x[i]+" ");}}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&&w[i]<=cleft){cleft=cleft-w[i];b=b+p[i];i++;}//装填剩余容量装满背包if(i<=n)b=b+p[i]/w[i]*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+w[i];if(wt<=c){if(cp+p[i]>bestp)bestp=cp+p[i];addLiveNode(up,cp+p[i],cw+w[i],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;j>0;j--){bestX[j]=(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 Element[n];double ws=0.0;double ps=0.0;for(int i=0;i<n;i++){q[i]=new Element(i+1,pp[i+1]/ww[i+1]);ps=ps+pp[i+1];ws=ws+ww[i+1];}if(ws<=c)return ps;}p=new double[n+1];w=new double[n+1];for(int i=0;i<n;i++){p[i+1]=pp[q[i].id];w[i+1]=ww[q[i].id];}cw=0.0;cp=0.0;bestX = new int[n+1];heap = new MaxHeap(n);double bestp = MaxKnapsack();for(int j=0;j<n;j++)xx[q[j].id]=bestX[j+1];return bestp;}public static void main(String [] args){double w[]=new double[5];w[1]=3;w[2]=5;w[3]=2;w[4]=1;double p[]=new double[5];p[1]=9;p[2]=10;p[3]=7;p[4]=4;double c=7;int x[] = new int[5];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(x[i]+" ");}//子空间中节点类型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;elsereturn 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==((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 HeapNode[maxNumber];}public static void put(HeapNode node){nodes[nextPlace] = node;nextPlace++;heapSort(nodes);}public static HeapNode removeMax(){HeapNode tempNode = nodes[1];nextPlace--;nodes[1] = nodes[nextPlace];heapSort(nodes);return tempNode;}private static void heapAdjust(HeapNode [] nodes,int s,int m) {HeapNode rc = nodes[s];for(int j=2*s;j<=m;j*=2){if(j<m&&nodes[j].upperProfit<nodes[j+1].upperProfit) ++j;if(!(rc.upperProfit<nodes[j].upperProfit))break;nodes[s] = nodes[j];s = j;}nodes[s] = 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 MAXNUM 100struct node{int step;double price;double weight;double max, min;unsigned long po;};typedef struct node DataType;struct SeqQueue{ /* 顺序队列类型定义 */int f, r;DataType q[MAXNUM];};typedef struct SeqQueue *PSeqQueue;PSeqQueue createEmptyQueue_seq( void ){PSeqQueue paqu;paqu = (PSeqQueue)malloc(sizeof(struct SeqQueue));if (paqu == NULL)printf("Out 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 queue.\n" );else{paqu->q[paqu->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->q[paqu->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 = p[j]/w[j];double b = p[j+1]/w[j+1];if (a < b){double temp = p[j];p[j] = p[j+1];p[j+1] = temp;temp = w[j];w[j] = w[j+1];w[j+1] = temp;}}}/* 求最大可能值*/double up(int k, double m, int n, double p[], double w[]) {int i = k;double s = 0;while (i < n && w[i] < m){m -= w[i];s += p[i];i++;}if (i < n && m > 0){s += p[i] * m / w[i];i++;}return s;}/* 求最小可能值*/double down(int k, double m, int n, double p[], double w[]) {int i = k;double s = 0;while (i < n && w[i] <= m){m -= w[i];s += p[i];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 < 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 = step;y.po = x.po << 1;if (y.min >= min){min = y.min;if (step == n) *po = y.po;}enQueue_seq(q, y);}if (x.weight+w[step-1]<= m){y.max = x.price + p[step-1]+up(step, m-x.weight-w[step-1], n, p, w);if (y.max >= min) {y.min = x.price + p[step-1] +down(step, m-x.weight-w[step-1], n, p, w); y.price = x.price + p[step-1];y.weight = x.weight + w[step-1];y.step = step;y.po = (x.po << 1) + 1;if (y.min >= min){min = y.min;if (step == n) *po = y.po;}enQueue_seq(q, y);}}}return min;}#define n 4double m = 7;double p[n] = {9, 10, 7, 4};double w[n] = {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 为 %d\n", i + 1, ((po & (1<<(n-i-1))) != 0)); printf("最优值是：%f\n", d);}getchar();return 0;}运行结果：。

0-1背包问题——回溯法求解【Python】回溯法求解0-1背包问题：问题：背包⼤⼩ w，物品个数 n，每个物品的重量与价值分别对应 w[i] 与 v[i]，求放⼊背包中物品的总价值最⼤。

回溯法核⼼：能进则进，进不了则换，换不了则退。

（按照条件深度优先搜索，搜到某⼀步时，发现不是最优或者达不到⽬标，则退⼀步重新选择）注：理论上，回溯法是在⼀棵树上进⾏全局搜索，但是并⾮每种情况都需要全局考虑，毕竟那样效率太低，且通过约束+限界可以减少好多不必要的搜索。

解决本问题思路：使⽤0/1序列表⽰物品的放⼊情况。

将搜索看做⼀棵⼆叉树，⼆叉树的第 i 层代表第 i 个物品，若剩余空间允许物品 i 放⼊背包，扩展左⼦树。

若不可放⼊背包，判断限界条件，若后续继续扩展有可能取得最优价值，则扩展右⼦树（即此 i 物品不放⼊，但是考虑后续的物品）。

在层数达到物品的个数时，停⽌继续扩展，开始回溯。

注：如何回溯呢？怎样得到的，怎样恢复。

放⼊背包中的重量取出，加在bagV上的价值减去。

约束条件：放⼊背包中物品的总质量⼩于等于背包容量限界条件：当前放⼊背包中物品的总价值（i及之前） + i 之后的物品总价值 < 已知的最优值这种情况下就没有必要再进⾏搜索数据结构：⽤⼀个变量记录当前放⼊背包的总价值 bagV（已扩展），⼀个变量记录后续物品的总价值 remainV（未扩展），当前已得到的⼀种最优值 bestV（全局情况），⼀个⽤0/1表⽰的数组bestArr[]记录哪些物品放⼊了背包。

核⼼结构：递归思路进⾏解决。

层层递归，递归到尽头，保留最优值，恢复递归中，层层回溯，即将原来加上去的重量与价值恢复。

# -*- coding:utf-8 -*-def Backtrack(t):global bestV, bagW, bagV,arr, bestArr, cntVif t > n: #某次深度优先搜索完成if bestV < bagV:for i in range(1, n+1):bestArr[i] = arr[i]bestV = bagVelse: #深度优先搜索未完成if bagW + listWV[t][0] <= w: #第t个物品可以放⼊到背包中，扩展左⼦树arr[t] = TruebagW += listWV[t][0]bagV += listWV[t][1]Backtrack(t+1)bagW -= listWV[t][0]bagV -= listWV[t][1]if cntV[t] + bagV > bestV: #有搜索下去的必要arr[t] = FalseBacktrack(t+1)if__name__ == '__main__':w = int(input()) #背包⼤⼩n = int(input()) #物品个数listWV = [[0,0]]listTemp = []sumW = 0sumV = 0for i in range(n):listTemp = list(map(int, input().split())) #借助临时list每次新增物品对应的list加⼊到listWV中sumW += listTemp[0]sumV += listTemp[1]listWV.append(listTemp) #依次输⼊每个物品的重量与价值bestV = 0bagW = 0bagV = 0remainV = sumVarr = [False for i in range(n+1)]bestArr = [False for i in range(n+1)]cntV = [0 for i in range(n+1)] #求得剩余物品的总价值,cnt[i]表⽰i+1~n的总价值 cntV[0] = sumVfor i in range(1, n+1):cntV[i] = cntV[i-1] - listWV[i][1]if sumW <= w:print(sumV)else:Backtrack(1)print(bestV)print(bestArr)print(cntV)检测：1052 65 34 52 43 617[False, True, False, True, False, True][24, 18, 15, 10, 6, 0]。

一、实验内容：分别用蛮力法、动态规划法、回溯法和分支限界法求解0/1背包问题。

注：0/1背包问题：给定种物品和一个容量为的背包，物品的重n C i 量是，其价值为，背包问题是如何使选择装入背包内的物品，使得装i w i v 入背包中的物品的总价值最大。

其中，每种物品只有全部装入背包或不装入背包两种选择。

二、所用算法的基本思想及复杂度分析：1.蛮力法求解0/1背包问题：1）基本思想：对于有n 种可选物品的0/1背包问题，其解空间由长度为n 的0-1向量组成,可用子集数表示。

在搜索解空间树时，深度优先遍历，搜索每一个结点，无论是否可能产生最优解，都遍历至叶子结点，记录每次得到的装入总价值，然后记录遍历过的最大价值。

2）代码:#include<iostream>#include<algorithm>using namespace std;#define N 100//最多可能物体数struct goods //物品结构体{int sign;//物品序号int w;//物品重量int p;//物品价值}a[N];bool m(goods a,goods b){return (a.p/a.w)>(b.p/b.w);}int max(int a,int b){return a<b?b:a;}int n,C,bestP=0,cp=0,cw=0;int X[N],cx[N];/*蛮力法求解0/1背包问题*/int Force(int i){if(i>n-1){if(bestP<cp&&cw+a[i].w<=C){for (int k=0;k<n;k++)X[k]=cx[k];//存储最优路径bestP=cp;}return bestP;}cw=cw+a[i].w;cp=cp+a[i].p;cx[i]=1;//装入背包Force(i+1);cw=cw-a[i].w;cp=cp-a[i].p;cx[i]=0;//不装入背包Force(i+1);return bestP;}int KnapSack1(int n,goods a[],int C,int x[]){Force(0);return bestP;}int main(){goods b[N];printf("物品种数n: ");scanf("%d",&n);//输入物品种数printf("背包容量C: ");scanf("%d",&C);//输入背包容量for (int i=0;i<n;i++)//输入物品i 的重量w 及其价值v {printf("物品%d 的重量w[%d]及其价值v[%d]:",i+1,i+1,i+1);scanf("%d%d",&a[i].w,&a[i].p);b[i]=a[i];}int sum1=KnapSack1(n,a,C,X);//调用蛮力法求0/1背包问题printf("蛮力法求解0/1背包问题:\nX=[ ");for(i=0;i<n;i++)cout<<X[i]<<" ";//输出所求X[n]矩阵printf("]装入总价值%d\n",sum1);bestP=0,cp=0,cw=0;//恢复初始化}3）复杂度分析：蛮力法求解0/1背包问题的时间复杂度为：。

课程名称：算法分析与设计设计题目：用回溯和分支限界求解0-1背包设计者：一、题目分析1.关于01背包给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为vi，0/1背包问题是如何选择装入背包的物品（物品不可分割），使得装入背包中物品的总价值最大。

2.回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。

这个开始结点就成为一个活结点，同时也成为当前的扩展结点。

在当前的扩展结点处，搜索向纵深方向移至一个新结点。

这个新结点就成为一个新的活结点，并成为当前扩展结点。

如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。

换句话说，这个结点不再是一个活结点。

此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。

回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。

二、总体设计0-1背包问题的形式化描述：给定c>0, wi>0, vi>0, 0<=i<=n，要求找到一个n元的0-1向量(x1, x2, ..., xn), 使得：max sum_{i=1 to n} (vi*xi),且满足如下约束：(1) sum_{i=1 to n} (wi*xi) <= c(2) xi∈{0, 1}, 1<=i<=n数据结构递归法：1.X={};2.flag=false;3.advance(1);4.if(flag)输出解X;else输出“无解”;advance(int k)循环执行下列操作1．对每一个x∈Sk（1） x=x;k加入X;（2）将xk（3）if(X是最终解)flag=true;return;（4）else if(X是部分解) advance(k+1);迭代法：1.X={};2.Flag=false;3.K=1;4.While(k>=1)(1)当(Sk没有被穷举)循环执行下列操作①xk=Sk 中的下一个元素;②将xk加入X;③if(X为最终解)flag=true;转步骤5;④else if(X是部分解)k=k+1;转步骤4;(2) 重置Sk，使得下一个元素排在第一位;(3)k=k-1;5.if(flag)输出解X;else输出“无解”;二、实验器材——实验环境Microsoft visual studio c++ 6.0三、制作步骤a.针对所给问题，定义问题的解空间；b.确定易于搜索的解空间结构；c.以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；四、程序代码递归1.#include<stdio.h>2.3.int c; //背包容量4.int n; //物品数5.int weight[100]; //存放n个物品重量的数组6.int price[100]; //存放n个物品价值的数组7.int cWeight=0; //当前重量8.int cPrice=0; //当前价值9.int bestPrice=0; //当前最优值10.int bestAnswer[100]; //当前最优解11.int bp=0;12.int bA[100]; //当前最优解13.int times=0;14.void Print();15.void Backtracking(int i)16.{17.times+=1;18. if(i>n)19. {20.Print();21.if(bestPrice>bp)22.{23.bp=bestPrice;24.for(int j=1;j<=n;j++)25.bA[j]=bestAnswer[j];26.}27.return;28.}29. if(cWeight+weight[i]<=c)30. { //将物品i放入背包，搜索左子树31.bestAnswer[i] = 1;32.cWeight += weight[i];33.bestPrice += price[i];34.Backtracking(i+1); //完成上面的递归，返回到上一结点，物品i不放入背包，准备递归右子树35.cWeight -= weight[i];36.bestPrice -= price[i];37. } bestAnswer[i] = 0;38. Backtracking(i+1);39.}40.41.void Print()42.{43. int i;44. printf("\n路径为{");45. for(i=1;i<n;++i)46.printf("%d,",bestAnswer[i]);47. printf("%d}\t价值为%d\n",bestAnswer[i],bestPrice);48.}49.50.void main()51.{52. int i;53. /*输入部分*/54.printf("请输入物品的数量:\n");55.scanf("%d",&n);56.printf("请输入背包的容量(能承受的重量):\n");57.scanf("%d",&c);58.printf("请依次输入%d个物品的重量:\n",n);59.for(i=1;i<=n;i++)60.scanf("%d",&weight[i]);61.printf("请依次输入%d个物品的价值:\n",n);62.for(i=1;i<=n;i++)63.scanf("%d",&price[i]);64. printf("各符合条件的路径为：\n");65. Backtracking(1);66. printf("*******************************************************\n");67. printf("\nthe best answer is {");68. for(i=1;i<n;++i)69.printf("%d,",bA[i]);70. printf("%d}\tthe price is %d\n",bA[i],bp);71.printf("\n\n总共搜索结点数%d\n",times);72.73.}运行结果：迭代# include <stdio.h>int c; //背包容量int m; //物品数int x[100];int weight[100]; //物品重量int price[100]; //物品价值int bp=0;int bA[100]; //当前最优解int times=0;void beibao(int n){int i,k;for (i=1; i<=n; i++) //初始化x[i]=0;k=1;while (k>=1){times+=1;x[k]=x[k]+1; //第k个物品放入背包if (x[k]<=2&& k==m){ //得到一个解，输出int currentWeight=0; //当前重量int currentPrice=0; //当前价值for (i=1; i<=n; i++){if(x[i]==1){currentWeight += weight[i];currentPrice += price[i];}}if(currentWeight<=c){if(currentPrice>bp){bp=currentPrice;for (int j=1; j<=n; j++){if(x[j]==2)bA[j]=x[j]-2;elsebA[j]=x[j];}}}}else if (x[k]<=2 && k<m)k=k+1; //放置下一个物品else{x[k]=0; //拿走第k个物品，重置x[k]，回溯k=k-1;}}}void main(){int i;/*输入部分*/printf("请输入物品的数量:\n");scanf("%d",&m);printf("请输入背包的容量(能承受的重量):\n");scanf("%d",&c);printf("请依次输入%d个物品的重量:\n",m);for(i=1;i<=m;i++)scanf("%d",&weight[i]);printf("请依次输入%d个物品的价值:\n",m);for(i=1;i<=m;i++)scanf("%d",&price[i]);beibao(m);printf("*******************************************************\n");printf("\nthe best answer is {");for(i=1;i<m;++i)printf("%d,",bA[i]);printf("%d}\tthe price is %d\n",bA[i],bp);printf("\n\n总共搜索结点数%d\n",times);}运行结果：六、方案比较※由表格可看出，递归法的搜索空间结点数要比迭代法少，因此递归法的空间性能好。

分⽀限界法解决01背包问题 分⽀限界法和之前讲的回溯法有⼀点相似，两者都是在问题的解的空间上搜索问题的解。

但是两者还是有⼀些区别的，回溯法是求解在解的空间中的满⾜的所有解，分⽀限界法则是求解⼀个最⼤解或最⼩解。

这样，两者在解这⼀⽅⾯还是有⼀些不同的。

之前回溯法讲了N后问题，这个问题也是对于这有多个解，但是今天讲的01背包问题是只有⼀个解的。

下⾯就讲讲分⽀限界法的基本思想。

分⽀限界法常以⼴度优先或以最⼩消耗（最⼤效益）优先的⽅式搜索问题的解空间树。

问题的解空间树是表⽰问题解空间的⼀颗有序树，常见的有⼦集树和排列树。

分⽀限界法和回溯法的区别还有⼀点，它们对于当前扩展结点所采⽤的扩展⽅式也是不相同的。

分⽀限界法中，对于每⼀个活结点只有⼀次机会成为扩展结点。

活结点⼀旦成为了扩展结点，就⼀次性产⽣其所有的⼦结点，⼦结点中，不符合要求的和⾮最优解的⼦结点将会被舍弃，剩下的⼦结点将加⼊到活结点表中。

再重复上⾯的过程，直到没有活结点表中没有结点，⾄此完成解决问题的⽬的。

分⽀限界法⼤致的思想就是上⾯的叙述，现在就可以发现，对于结点的扩展将会成为分⽀限界法的主要核⼼。

所以，分⽀限界法常见的有两种扩展结点的⽅式，1.队列式（FIFO）分⽀限界法，2.优先队列式分⽀限界法。

两种⽅法的区别就是对于活结点表中的取出结点的⽅式不同，第⼀种⽅法是先进先出的⽅式，第⼆种是按优先级取出结点的⽅式。

两中⽅法的区别下⾯也会提到。

在背包问题中还会提到⼀个⼦树上界的概念，其实就是回溯法中的剪枝函数，只不过，分⽀限界法⾥的剪枝函数改进了⼀些，剪枝函数同样也是分⽀限界法⾥⽐较重要的东西。

下⾯就讲⼀讲01背包问题的实现。

01背包问题和前⾯讲的背包问题的区别不⼤，就是01背包问题的物品不可以只放⼊部分，01背包问题的物品只能放⼊和不放⼊两个选择，这也是名字中01的原因。

其他的和背包问题相差不⼤，这⾥也不再累述。

算法的主体是⽐较容易想的，⾸先，将数据进⾏处理，这也是上⾯讲到的第⼆种取结点的⽅式（优先队列式）。