背包 算法

public class Bag {
 List list;
 public Bag(){
  list=new ArrayList();
 }
 public static void main(String[] args) {
  Bag bg=new Bag();
  int[] bagArr=new int[]{2,4,6,9,10,16};
  bg.bagList(12, bagArr, 0,new int[bagArr.length]);
  
  for(Object obj:bg.getList()){//显示所有的满足条件的组合
   int[] ob=(int[])obj;
   for(int n:ob){
    if(n==0) break;
    System.out.print(n+"   ");
   }
   System.out.println();
  }
  
 }

 void bagList(int total,int[] src,int offset,int[] bag){
  if(total==0){
   list.add(bag);
   return;
  }
  while(offset<src.length&&total<src[offset]) offset++;  //从起始值开始寻找第一个小于要求增加重量的数值  
  if(offset>=src.length) return ;
  bagList(total,src,offset+1,bag.clone());                           // 背包中含有offset位置的 
  bagList(total-src[offset],src,offset+1,put(bag,src[offset]));   //背包中不含有offset位置
 }
 
  int[] put(int[] bag,int n){
  int pos=-1;
  while(bag[++pos]>0);
  bag[pos]=n;
  return bag;
 }
 
 public List getList(){
  return list;
 }
}