fracknap.java

算法导论上机作业java实现

public class FracKnap {
	 int Allweight = 100;
	 int remainweight = Allweight;
	 public static int[] FacKnap(int number,int Allweight)
	 {
		 int remainweight = Allweight;
		 int[] value = {200,180,225,200,50};
		 int[] weigh = {50,30,45,25,5};
		 int[] costperformance = new int [number];  //单位价值
		 int[] symbol = {0,0,0,0,0};   //标志数组，用来表示第i个数的单位价值排在第几位
		 int temp =0;
		 int[] seal = {0,0,0,0,0};
		 //标志数组，用来标志第i个物体是拿还是不拿还是只拿一部分，seal[i]=1表示全拿，
		 //seal[i]的值大于1的第以个数对应的物体只拿一部分，seal[i]表示其他的值时候则不拿
		 for(int i=0;i<number;i++)   //求单位价值
			 costperformance[i] = value[i]/weigh[i];
		 for(int sign=1;sign<number+1;sign++)//求出第i个物体的单位价值在第几位
		 {
			 temp = 0;
			for(int i=0;i<number;++i)
			{
				
				if(symbol[i]==0)
					if(temp < costperformance[i])
						temp = costperformance[i];
			}
			for(int i=0;i<number;++i)
			{
				if(temp == costperformance[i])
					symbol[i] = sign;
			}
		 }
		 for(int sign=1;sign<number+1;sign++)//该循环为标志数组seal[]赋值，用于该函数的返回值
		 {
		     for(int i=0;i<number;i++)
		     {
			    if(symbol[i]==sign)
			    {
			    	if(remainweight>=weigh[i])
			    	    {
			    		  seal[i] = 1;
			    	      remainweight  -= weigh[i];
			    	    } 
			    	else
			    	{
			    		seal[i] = sign;//只所以这样做是为了确定哪一个物体只拿以部分，满足条件的应该是第一个大于1的数
			    		break;
			    	 }
			      }
		     }
		 }
		 return seal;
	 }
	public static void main(String[] args) {
		
		int counter = 0;//用于有多少个物体被拿了的计数
		int[] weigh = {50,30,45,25,5};
		int[] seal=FacKnap(5,100);//函数返回值赋给seal[]
		int remainweight = 100;
		for(int i=0;i<5;i++)
		{
			if(seal[i]==0)
				System.out.println("The number of:"+(i+1)+"hadn't be taken");
			else
				if(seal[i]==1)
					{
					System.out.println("The number of:"+(i+1)+"had be taken");
					remainweight -= weigh[i];
					counter +=1;
					}
		}
		for(int i=0;i<4;i++)	 //必须多用这个for循环，因为要用到上面循环改过的remainweight的值
		{
			 if(seal[i]==counter + 1)
			 System.out.println("The number of:"+(i+1)+"had be taken some!And the weight be taken is:"+remainweight);
			 else
				 if(seal[i] >counter+1)//不能把这个语句放在上面一样输出语句去一起判断，因为需要counter的值
					 System.out.println("The number of:"+(i+1)+"hadn't be taken");
			 
		}
		}

	}