遡及解0-1リュックサック

遡及法は本質的に状態空間ツリーを優先的に探索するアルゴリズムである.
 
剪断関数(拘束関数+限界関数)を導入しない場合は、窮屈なアルゴリズムです.
 
適切な限界関数を導入し,最適な答えの接点を含まないと確信したサブツリーを切り取り,啓発的アルゴリズムにした.
 
表示制約:xi=1はi番目のアイテムをリュックに入れることを示し、xi=0はi番目のアイテムがリュックに入らないことを示します.暗黙的な制約:
 
解空間サイズは2 nである.解空間ツリーは高さn+1の満二叉木である.
 
下限関数:変数Lの初期値は0であり、1つの答えのノードに遭遇すると、その答えのノードの収益値fpが計算され、L=max{L,fp}となる.Lには,これまでに探索された解答ノードでの収益の最大値が常に保持され,0/1リュックの最適解値は必ずL以上であるため,最適解値の下限推定値はLである.
 
限界関数:状態空間ツリーのいずれかのノードXであり、その上界関数値bp<最適解値の下界推定値変数Lであれば、Xサブツリーに最適解ノードが含まれていないと断定し、Xをルートとするサブツリーを切り取ることができる.最適解を含まない枝分かれを切り取る【検索した答えノードの収益最大値よりどうしても小さい】
 
上界関数:現在状態空間ツリーのノードXに位置し、cwはリュックの現在の重量、cpは現在リュックに組み込まれている物品の総収益であり、貪欲法は残荷重と残物品構成の一般的なリュック問題(物品番号k+1、k+2,...,n-1、荷重M-cw)の最大収益をrpとする.Xをルートとするサブツリー上のすべての可能な答えノードのターゲット関数値がbp=cp+rpを超えることは不可能であるため、ノードXの上界関数値はbpである.
 
例8−4には、0/1バックパックn=8,M=110,(w 0,w 1,...,w 7)=(1,11,21,23,33,43,45,55),(p 0,p 1,...,p 7)=(11,21,31,33,43,53,55,65)が設けられている.pi/wi非増幅配列、すなわちpi/wi≧pi+1/wi+1
まとめ:左へ引いてはいけない解の分岐【ステルス拘束を満たさない】右へ引いて最適解を含まない【どうしてもLより小さい】
Javaコードを次に示します

public class Packet {
	
	public int []w;
	
	private int m;
	
	private int n;
	
	public int []p;
	
	public int fp;
	
	
	public Packet()
	{
		w=new int[]{30,10,20,50,40};
		p=new int[]{65,20,30,60,40};
	}
	public static void main(String args[])
	{
		Scanner input=new Scanner(System.in);
		Packet p=new Packet();
		int []x=new int [5];
		int []y=new int [5];
		p.m=100;
		p.n=5;
		p.BKnapsack(0, 0, 0, x, y);
		for(int i=0;i<5;i++)
		{
			System.out.println(x[i]);
		}
	}

	public int Bound(int k,int cp,int cw)
	{
		int b = cp, c = cw; //     cp       cw  （xk=0）
		for (int i = k + 1; i < n; i++) //               
		{
			c += w[i];
			if (c < m)
				b += p[i]; //  i         
			else
				return b ;
		}
		return b;

	}
	
	
	public void BKnapsack(int k,int cp,int cw,int []x,int []y)
	{
		if (cw+w[k]<=m)	//   ，         ，        
		   {
			y[k]=1;
			if (k<n-1) 		
			{
				BKnapsack(k+1,cp+p[k],cw+w[k],x,y);
			}
			if (cp+p[k]>fp && k==n-1)	//    
			{	fp=cp+p[k];		//          
				for (int j=0;j<=k;j++) x[j]=y[j];
			}
		   }
		 if (Bound(k,cp,cw)>=fp) //   ，         ，        
		   {
			y[k]=0;
			if (k<n-1) 		//   
				BKnapsack(k+1,cp,cw,x,y);	
			if (cp>fp && k==n-1)	//    
			{	fp=cp;		//          
				for (int j=0;j<=k;j++) x[j]=y[j];
			}
		   }
	}


}