背包问题之贪心算法实现

Code:

1. package algorithm;  
2.   
3. /** 
4. *   利用贪心算法，对背包问题的java实现 
5. */  
6. public class Knapsack {  
7.       
8.     private float m ;   //背包容量  
9.     private float[] v ; //三个物品的价值  
10.     private float[] w ; //三个物品的质量  
11.     private float[] x ; //往背包装东西的比例  
12.     private int n ;     //物品个数  
13.     double[] p_w_v ;    //每个物品的单位重量价值  
14.       
15.     public Knapsack(){  
16.           
17.         this.m = 50.0f ;    //背包容量为50  
18.         this.v = new float[]{60.0f,120.0f,100.0f} ; //三个物品的价值分别为60,120,100  
19.         this.w = new float[]{10.0f,30.0f,20.0f} ;   //三个物品的质量分别是10,30,20  
20.         this.x = new float[3] ;     //往背包装东西的比例  
21.         this.n = 3 ;                //三个物品  
22.         this.p_w_v = new double[n] ;    //每个物品的单位重量价值  
23.     }  
24.       
25.     //对物品的单位重量价值进行排序  
26.     public void sort(int n , float[] v ,float[] w)throws Exception{  
27.   
28.         for (int i = 0 ; i < n ; i++){  
29.             p_w_v[i] = v[i] / w[i] ;  
30.         }  
31.         print (p_w_v);  
32.         System.out.println ("");  
33.         insertSort(p_w_v,w,v) ;  
34.         print (p_w_v);  
35.     }  
36.       
37.     public void print (double a[]){//打印输出数组    
38.         int len = a.length;    
39.         for (int i = 0; i < len; i++){    
40.             System.out.print(a[i] + " ");    
41.         }    
42.     }  
43.       
44.     public void print (String str){//打印输出数组    
45.         System.out.print(str + "/n");    
46.     }  
47.   
48.     public void insertSort(double[] a , float[] b , float[] c){//排序静态函数，实现排序功能    
49.         int len = a.length;//获得数组长度    
50.         double temp;//临时变量，用于交换值    
51.         float w_temp ;  
52.         float v_temp ;  
53.         for (int i = 0; i < len-1; i++){   //通过循环实现主要算法    
54.             for (int j = 0; j < len-1-i; j++){    
55.                 if (a[j+1] > a[j]){    //如果后一下值比前一个值大，则交换两个值的大小，    
56.                       
57.                     temp = a[j+1];    //很显然是从大到小排序    
58.                     w_temp = w[j+1];  
59.                     v_temp = v[j+1];  
60.                       
61.                     a[j+1] = a[j];    
62.                     w[j+1] = w[j];  
63.                     v[j+1] = v[j];  
64.                       
65.                     w[j] = w_temp;    
66.                     v[j] = v_temp;    
67.                 }    
68.             }    
69.         }  
70.     }  
71.   
72.      //贪心算法核心思想  
73.     public void knapsack()throws Exception{  
74.         sort (n , v , w) ;  
75.         int i ;  
76.         for (i = 0 ; i < n ; i++){  
77.              x[i] = 0 ;  
78.         }  
79.         float c = m ;  
80.         for (i = 0 ; i < n ; i++){  
81.              if (w[i] > c){  
82.                   break ;  
83.              }  
84.              x[i] = 1 ;  
85.              c -= w[i] ;  
86.         }  
87.         if (i < n){  
88.              x[i] = c / w[i] ;  
89.         }  
90.         print ("/n物品一可以装入的比例: " + x[0]);  
91.         print ("物品二可以装入的比例: " + x[1]);  
92.         print ("物品三可以装入的比例: " + x[2]);  
93.         print ("可以装入的最大价值为: " + (x[0]*v[0] + x[1]*v[1] + x[2]*v[2]));  
94.         print ("可以装入的最大重量为" + (x[0]*w[0] + x[1]*w[1] + x[2]*w[2]));  
95.     }  
96.       
97.     public static void main (String[] args)throws Exception{  
98.         Knapsack ksp = new Knapsack();  
99.         ksp.knapsack();  
100.     }  
101. }