0 1背包问题贪心算法解决0-1背包问题得到的解通常是最优解或者近似最优解吗

回朔法、分支限界法解0-1背包问题程序，要完整的，可执行的。限JAVA或C语言编写

Java回溯法： package sun; import java.util.*; public class Knapsack0{ /* 用回溯法解决0-1背包问题 */ private double[] p,w;//分别代表价值和重量 private int n; private double c,bestp,cp,cw; private int x[]; //记录可选的物品 private int[] cx; public Knapsack0(double pp[],double ww[],){ this.p=pp;this.w=ww;this.n=pp.length-1; ;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=5"); System.out.println("*****背包容量：c=10"); System.out.println("*****物品重量数组：ww= {2,2,6,5,4}"); System.out.println("*****物品价值数组：vv= {6,3,5,4,6}"); 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[]={6,3,5,4,6}; double w[]={2,2,6,5,4}; int maxweight=10; Knapsack0 ks=new Knapsack0(p,w,maxweight); ks.knapsack(); //回溯搜索 ks.printResult(); } } 分支限界法： package sun; public class knapsack1 { 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[],,int xx[]){ //返回最大值，bestX返回最优解 ; 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[6]; w[1]=2;w[2]=2;w[3]=6;w[4]=5;w[5]=4; double v[]=new double[6]; v[1]=6;v[2]=3;v[3]=4;v[4]=5;v[5]=6; double c=10; int x[] = new int[6]; double m = knapsack(v,w,c,x); System.out.println("*****分支限界法*****"); System.out.println("*****物品个数：n=5"); System.out.println("*****背包容量：c=10"); System.out.println("*****物品重量数组：w= {2,2,6,5,4}"); System.out.println("*****物品价值数组：v= {6,3,5,4,6}"); System.out.println("*****最优值：="+m); System.out.println("*****选中的物品是:"); for(int i=1;i<=5;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 pareTo(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 pareTo(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); } } } 不知道你是哪的学生， 此乃郑州轻工业学院考试试题， 并且还未上交， 抄的时候小心点， 参考一下就可以了， 不要全抄， 版权所有违者必究！！！！！！！！！ 哈哈哈哈 ！！！

贪心算法解决0-1背包问题得到的解通常是最优解或者近似最优解吗

这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑n=2, w=[100,10,10], p =[20,15,15], c = 105。当利用价值贪婪准则时，获得的解为x= [ 1 , 0 , 0 ]，这种方案的总价值为2 0。而最优解为[ 0 , 1 , 1 ]，其总价值为3 0。 (ii)另一种方案是重量贪婪准则是：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n= 2 ,w=[10,20], p=[5,100], c= 2 5。当利用重量贪婪策略时，获得的解为x =[1,0], 比最优解