回溯法 01背包

本文主要是介绍回溯法 01背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题太经典，就不描述问题了，以前都是用动态规划做的，blog上也有，现在看看回溯法的程序：

/*** 		01背包的回溯解法*/
public class BeiBao01 {static int c;    //背包容量static int n;    //对象数目static int[] w;  //对象重量数组static int[] p;  //对象收益数组static int cw;   //当前背包重量static int cp;   //当前背包价值static int bestp;//迄今最大的收益static int[] X;  //记录在书中的移动路径public static void main(String args[]) {c=30;n=3;w=new int[]{20,15,15};p=new int[]{40,25,25};X=new int[3];getBest(0);System.out.println(bestp);}public static void getBest(int i){if(i>=n){if(cp>bestp){bestp=cp;}return;}if(cw+w[i]<=c){X[i]=1;cw+=w[i];cp+=p[i];getBest(i+1);cw-=w[i];cp-=p[i];}X[i]=0;getBest(i+1);}
}

这篇关于回溯法 01背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---