回溯法解决 0-1 背包问题 package chapter11; import java.util.Arrays; public class Ch11_11 { //背包容量 private int c; //物品重量数组 private int[] w; //物品价值数组 private int[] v; //记录结果 private int[] x; //记录最优解 private int[] jie; //记录背包所装物品的最大值 private int maxValue; public Ch11_11(int[] w, int[] v, int c){ this.w = w; this.v = v; this.c = c; x = new int[w.length]; jie=new int[w.length]; } public void DP(int n){ if(n==w.length){ if(heFa(x)){ printJie(x); } }else{ for(int i=0;i<2;i++){ x[n]=i; DP(n+1); } } } /** * 判断当前的结果x是不是合法的 * 所装物品的重量和超过背包容量就非法 * @param x2 * @return 真还是假 */ private boolean heFa(int[] x2) { int result=0; for(int i=0;i<x2.length;i++){ if(x[i]==1) result+=w[i]; } if(result>c) return false; else return true; } /** * 打印出符合条件的所有解 * 并且将最大值存到maxValue中,将最大值的数组存放到jie中 * @param x2 * @return */ private void printJie(int[] x2) { System.out .println(Arrays.toString (x)); int sum=0; for(int i=0;i<x2.length;i++){ if(x[i]==1) sum+=v[i]; } maxValue=maxValue>sum?maxValue:sum; if(maxValue<=sum) System.arraycopy (x2, 0, jie, 0, x2.length); } public static void main(String[] args) { int[] w = {6, 5, 2, 1, 1};//物品重量 int[] v = {48, 40, 12, 8, 7};//物品价格 int c=8; //背包容量 Ch11_11 ch=new Ch11_11(w,v,c); System.out .println(“全部解如下：”); ch.DP(0); System.out .println(“最优解是：”+Arrays.toString (ch.jie)+”\n最大值 是：”+ch.maxValue); } }