newbag.java

动态规划策略实现0-1背包问题的JAVA源程序

public class newBag{
	public newBag(){}
	public int[][] putbag(int[]w,int[]v,int c,int n){
		int temp1,temp2;
		int i,j,p,q;
		int sum=0;
		int [][]V=new int[n+1][c+1];
		for(i=0;i<=n;i++)
			V[i][0]=0;
		for(j=0;j<=c;j++)
			V[0][j]=0;
		for(int s=1;s<=min(w[1]-1,c);s++)
			V[1][s]=0;
		for(int t=w[1];t<=c;t++)
			V[1][t]=v[1];
		for(p=1;p<=n;p++)
		{
			for(q=1;q<=min(w[p]-1,c);q++)
				V[p][q]=V[p-1][q];
			for(q=w[p];q<=c;q++)
			{
				temp1=V[p-1][q];
				temp2=V[p-1][q-w[p]]+v[p];
				V[p][q]=max(temp1,temp2);
			}
		}

		return V;
	}
	
	public int max(int x,int y){
		if(x>=y)
			return x;
		else
			return y;
	}
	public int min(int x,int y){
		if(x<=y)
			return x;
		else
			return y;
	}
	
	
	public void putin(int[][]V,int[]w,int c,int n,int []take){
		for(int i=n;i>1;i--)
			if(V[i-1][c]==V[i][c])
				take[i]=0;
			else
			{
				take[i]=1;
				c-=w[i];
			}
		if(V[1][c]!=0)
			take[1]=1;
		else
			take[1]=0;
	}
	
	
	public void display(int[]w,int[]v,int[]put){
		int sumV=0;
		int sumW=0;
		int n=50;
		int c=1000;
		for(int i=1;i<put.length;i++)
		{
			if(put[i]==1)
			{
				System.out.print("w"+(i)+":"+w[i]+"  ");
				sumW+=w[i];
			}
		}
		System.out.println();
		for(int i=1;i<put.length;i++)
		{
			if(put[i]==1)
			{
				System.out.print("v"+(i)+":"+v[i]+" ");
				sumV+=v[i];
			}
		}
		System.out.println();
		System.out.println("sumValue:"+sumV);
		System.out.println("sumWight:"+sumW);
	}
	
	public int count(char[]x){
		int count1=0;
		for(int s=0;s<x.length;s++)
			if(x[s]==',')
				count1++;
		return count1;
	}
	
	public void charToInt(char[]x,int[]y){
		int count=0;
		for(int s=0;s<x.length;s++)
			if(x[s]==',')
				count++;
		int i=0,j=0;
		while((i<x.length)&(j<count+1))
		{
			if(x[i]!=',')
			{
				y[j]=(int)(x[i]-'0');
				for(int k=i+1;k<x.length;k++)
				{
					if(x[k]==',')
					{
						i=k+1;
						break;
					}
					else
						y[j]=y[j]*10+(int)(x[k]-'0');
				}
				j++;
			}
			//else
			//{
				//j++;
				//continue;
			//}

		}
	}
	
	public static void main(String[]args){
		
		int []w={0,80,82,85,70,72,70,
				 66,50,55,25,50,55,
				 40,48,50,32,22,60,
				 30,32,40,38,35,32,
				 25,28,30,22,50,30,
				 45,30,60,50,20,65,
				 20,25,30,10,20,25,
				 15,10,10,10,4,4,2,1};
		int []v={0,220,208,198,192,180,180,
				 165,162,160,158,155,130,
				 125,122,120,118,115,110,
				 105,101,100,100,98,96,
				 95,90,88,82,80,77,
				 75,73,70,69,66,65,
				 63,60,58,56,50,30,
				 20,15,10,8,5,3,1,1};
				 
		//int []w={0,3,5,7,8,9};
		//int []v={0,4,6,7,9,10};
		int n=50;
		int c=1000;
		int [][]V=new int[n+1][c+1];
		int sumValue=0;
		int []take=new int[n+1];
		newBag newbag=new newBag();
		V=newbag.putbag(w,v,c,n);
		newbag.putin(V,w,c,n,take);
		newbag.display(w,v,take);
		//for(int i=1;i<=n;i++)
		sumValue+=V[n][c];
		//System.out.println("sumV:"+sumValue);
		System.out.println("sumV:"+V[n][c]);
	}
	
}