java 递归算法 背包问题.txt

简单的背包问题

java　递归算法　背包问题！！ 
背包问题.设有一个背包可以放入物品的重量为s，现在n件物品，重量分别为w［０］，w［１］......w［n－１］.问题是能否从这n件物品中选择若干件放入此背包中使得放入的重量之和正好等于s.　如果存在一种符合上述要求的选择，则称此背包问题有解;否则称此背包问题无解.　试用分而治之的算法设计求解背包问题的函数.　 
　　提示：此背包问题的递推定义如下(其中true表示有解，false表示无解)： 
knap(s,n)={true s=0 此时问题有解 
knap(s,n)={ flase s<0 总重量不能为负解 
knap(s,n)={flase s>0且n<1 物品件数不能为负数 
knap(s,n)={knap(s,n-1) s>0且n>=1 所选物品不包括w[n-1]时 
knap(s,n)={knap(s-w[n-1],n-1) s>0且n＞=1 所选物品包括w[n-1]时 

public void beibao(int[] intArray,int start,int sum){ 
//参数说明 
//intArray：从大到小排序的物品重量数组 
//start:从数组的哪一个元素开始往包里面放 
//sum:包能够装的重量 
if(start >= intArray.length){ 
System.out.println("此题无解"); 
return; 
} 
if(intArray[start] > sum){ 
this.beibao(intArray,start+1,sum); 
}else if(intArray[start] == sum){ 
System.out.println("此题有解"); 
return; 
}else{ 
this.beibao(intArray,start+1,sum-intArray[start]); 
} 
} 
又复习了一遍分治法，如果要记录下放进包里的是哪几件物品，还要想一想。。。。。 

*
 * Created on 2006-11-13
 *
 * TODO To change the template for this generated file go to
 * Window - Preferences - java - Code Style - Code Templates
 */
package net.dzf.fenzhifa;
 
/**
 * @author dengzhangfan
 * 用分治法解决背包问题
 *
 * TODO To change the template for this generated type comment go to
 * Window - Preferences - java - Code Style - Code Templates
 */
 
public class fenzhifa {
 
 private static fenzhifa obj = new fenzhifa();
 
 public void beibao(int[] intArray,int start,int left,int sum){
  //参数说明
  //intArray：从大到小排序的物品重量数组
  //start:从数组的哪一个元素开始往包里面放
  //left:包还能装的重量
  //sum:包能够装的总重量
  if(intArray.length == 0){
   System.out.println("无解");
   return;
  }
  if(start == intArray.length){
   System.out.println("回朔开始");
   int[] another = new int[intArray.length - 1];
   for(int i=0;i<another.length;i++){
    another[i] = intArray[i+1];
   }
   obj.beibao(another,0,sum,sum);
  }
  else if(intArray[start] > left){
   obj.beibao(intArray,start+1,left,sum); 
  }else if(intArray[start] == left){
   System.out.println("此题有解");
   return;
  }else{
   obj.beibao(intArray,start+1,left-intArray[start],sum);
  }
 }
 
 
 public static void main(String[] args){
     int[] intArray = {9,8,5,3,2};
     obj.beibao(intArray,0,15,15);
 }
 
 
}


public class Test { 
/** 
* 返回给定数组中除去第一个元素后的子数组 
* @param intArray 
* @return 
*/ 
private static int[] getSubArray(int[] intArray) { 
int[] another = new int[intArray.length - 1]; 
for (int i = 0; i < another.length; i++) { 
another[i] = intArray[i + 1]; 
} 
return another; 
} 

/** 
* 返回一个背包问题是否有解 
* @param intArray 物品重量数组(无需排序) 
* @param sum 包能够装的总重量 
* @return 
*/ 
private static boolean beibao2(int[] intArray, int sum) { 
if (intArray.length == 0) 
return false; 
if (intArray[0] == sum) { 
return true; 
} else if (intArray[0] > sum) { 
return beibao2(getSubArray(intArray), sum); 
} else { 
if (beibao2(getSubArray(intArray), sum - intArray[0])) { 
return true; 
} else { 
return beibao2(getSubArray(intArray), sum); 
} 
} 
} 

public static void main(String[] args) { 
int[] intArray = { 9, 6, 5, 4, 2 }; 
String result = beibao2(intArray, 16) ? "有解" : "无解"; 
System.out.println(result); 
} 
}