knapsack.java

算法导论上机作业java实现

public class knapsack {
 public static int[] Knapsack (int number,int Allweight)
 {
	 int weight=1;
	 int[] value = {200,180,225,200,50};
	 int[] weigh = {50,30,45,25,5};
	 int[] symbol = new int [number];
	 int[][] count = new int[5][100];
	 for(weight=0;weight<Allweight;weight++)
		 count[0][weight] = 0;
	 for(int i =1;i<number;i++)
	 {
		 count[i][0] = 0;
		 for(weight=1;weight<Allweight;weight++)
		 {
			 if(weigh[i] <=weight)
			 {
				 if(value[i]+count[i-1][weight-weigh[i]]>count[i-1][weight])
				 {
					 count[i][weight] = value[i]+count[i-1][weight-weigh[i]];
					 symbol[i] = 1;
				 }
				 else
				 {
					 count[i][weight]=count[i-1][weight];
					 symbol[i] = 0;
				 }
			 }
			 else{
				 count[i][weight] = count[i-1][weight];
			     symbol[i] = 0;	 
			 }
		 }
		 
	 }
	 return symbol;
 }
	public static void main(String[] args) {
		//System.out.print("the items should be taken is:");
		int[] symbol = Knapsack (5,100);
		for(int i=0;i<5;i++)
		{
			switch(i+1)//为了让函数输出第几个事件而不是i事件，呵呵，玩而已
			{
			case 1:System.out.print("The first goods ");break;
			case 2:System.out.print("The second goods ");break;
			case 3:System.out.print("The third goods ");break;
			case 4:System.out.print("The forth goods ");break;
			case 5:System.out.print("The fifth goods ");break;
			default:break;
			}
			if(symbol[i]==0)
				System.out.println("hadn't be taken");
			else
				System.out.println("has be taken");
				
				
		}
		
	}
		
}