1、0/1背包问题： 有一组物品，其数量分别是w1,w2,wn;其价值是v1,v2,vn；现有一容量为C的背包，现问该如何人装物品才能使背包价值最大化。 依旧可以用子集树解决问题：因为只有背包容量一个限制，所以我们以物品重量为基准，用回溯算法解决此问题。
static int[] w={5,8,7,9,6};//重量 static int[] v={12,9,13,10,11};//价值 static int c=18;//背包容量 static int brr[]=new int[w.length];//标记数组 static int best[]=new int[w.length];//最优解数组 static int CV;//已选择物品的价值 static int CW ;//已选择物品的重量； static int LV=0;//剩余商品价值 static int bestvalue=Integer.MIN_VALUE;//物品最优价值 public static void main(String[] args) { for(int i=0;i<v.length;i++){ LV+=v[i];//先计算总价值 } pak(0); System.out.println(bestvalue); System.out.println(Arrays.toString(best)); } public static void pak(int i){ if( i==w.length){ if(CV>bestvalue){ bestvalue=CV; for(int j=0;j<w.length;j++){ best[j]=brr[j]; } } }else { LV-=v[i];//剩余价值-已选中价值 if(CW+w[i]<=c){//当前重量符合要求重量 CV+=v[i];//当前价值加上选中价值 CW +=w[i];//选择第i个//当前重量加上选中重量 brr[i]=1;//i节点的左孩子 pak(i+1); CV-=v[i];//不选择第i个，返回之前的结果 CW -=w[i]; } if(CV+LV>bestvalue){//如果选中价值+剩余价值》最优解，才有去右子树的必要 brr[i]=0;//i节点的右孩子 pak(i+1); } LV+=v[i]; } }2、轮船装载问题： 有一组物品：重量w1,w2,w3, 现有两艘船，容量分别为C1 C2， 且满足W1+w2+…<=C1+C2，求C1 C2。 可以参考上面的0/1背包的思想，依旧用回溯算法来解：
static int[] w = {12, 18, 21, 14, 9, 10}; static int c1 = 55; static int c2 = 34; static int cw = 0;//已选择物重量 static int rw = 0;//未选择物品 static int bestv = Integer.MIN_VALUE; static int[] brr = new int[w.length]; static int[] best = new int[w.length]; public static void load(int i) { if (i == w.length) { if (cw > bestv) { bestv = cw; for (int j = 0; j < brr.length; j++) { best[j] = brr[j]; } } } else { rw -= w[i];//右树枝剪枝 if (cw + w[i] <= c1) {//左树枝剪枝 cw += w[i]; brr[i] = 1; load(i + 1); // 选择第i个节点；过了这个节点后就要向上回溯 cw -= w[i];//把回溯掉的点的重剪掉 } if (cw + rw > bestv) {//右边的节点才有去往的必要 brr[i] = 0; // 才有必要去往右边的i节点 load(i + 1); // 没选择第i个节点 } rw += w[i]; } } public static void main(String[] args) { for (int i = 0; i < w.length; i++) { rw += w[i]; } load(0); int sum = 0; for (int i = 0; i < best.length; i++) { if (best[i] == 0) { sum += w[i]; } } if (sum > c2) { System.out.println("物品无法装载到轮船!"); return; } System.out.println("C1:" + c1 + "装载物品:"); for (int i = 0; i < best.length; i++) { if (best[i] == 1) { System.out.print(w[i] + " "); } } System.out.println(); System.out.println("C2:" + c2 + "装载物品:"); for (int i = 0; i < best.length; i++) { if (best[i] == 0) { System.out.print(w[i] + " "); } } System.out.println(); }