tanxinfa1.java

0-1背包问题,按价值最大为标准时划分的.

import com.cn.*;
public class Tanxinfa1{
 public static  void main(String args[]){
 	float p[] = new float[args.length];
 	for(int i=0;i<args.length;i++)
 	  p[i] = Float.parseFloat(args[i]);
 	  float z[] = new float[1];
 	  float w[] = new float[(args.length-1)/2];
 	  float v[] = new float[(args.length-1)/2];
 	  
 	  System.arraycopy(p,1,w,0,(args.length-1)/2);
 	  System.arraycopy(p,(args.length-1)/2+1,v,0,(args.length-1)/2);
 	  System.arraycopy(p,0,z,0,1);
 	 float c = z[0];
 	      int n = v.length;
          System.out.println("包的容量为:"+c);
 	     System.out.print("物品的重量分别为：");
 	    for(int i=0;i<w.length;i++)
 	       System.out.print(w[i]+" ");
 	       System.out.println("");
 	     System.out.print("物品的价值分别为：");
 	    for(int i=0;i<v.length;i++)
 	      System.out.print(v[i]+" ");
 	     Element [] d = new Element[n];
 	     for(int i=0;i<d.length;i++){
 	          d[i]= new Element(w[i],v[i]);
 	          }
 	     MergeSort.mergeSort(d);
 	      float opt=0;
 	      int i;
 	    for(i=0;i<d.length;i++){
 	     	if(d[i].w>c) break;
 	     	opt+=d[i].v;
 	      	c-=d[i].w;
 	      	}
 	      	if(i<n)
 	        {
 	        	 opt+=c/d[i].w*d[i].v;
 	      	}
 	      System.out.println("");
 	      System.out.println("按价值最大为标准时，包的总价值为："+opt);
 	      }
 	  }
 class Element implements Comparable{
 	      	float  w;
 	      	float v;
 	      
 	public Element(float  ww,float vv){
 	      		w=ww;
 	      		v=vv;
 	      }
 	      public int compareTo(Object o){
          float ov =((Element)o).v;
          if(v>ov) return -1;
          if(v==ov) return 0;
          return 1;
 	      			
 	      			}
 	      		}