Go语言视频零基础入门到精通

javalearner

用动态规划法求解0―1背包问题，并输出问题的最优解。
0―1背包问题描述如下：
      给定m种物品和一背包。物品i的重量是w，其价值为v，背包的容量是c，问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。(每种物品只能选择放入0/1次背包）  

1. public class Knapsack
   
2. {
   
3.     public static void knapsack(int[] v, int[] w, int c, int[][] m)
   
4.     {
5.          
   
6.         int n = v.length-1;
7. 
   
8.         /** v[] w[] c 分别是价值、重量数组和背包容量,
9.          m[i][j]表示只有w[i],w[i+1]...w[n]这些物品时，背包容量为j时的最大价值。*/
   
10.       
    
11.         int jMax = Math.min(w[n]-1, c);
    
12.         for(int j = 0; j <= jMax; j++)  
    
13.             m[n][j] = 0;        //当w[n]>j 有 m[n][j]=0
    
14.         //m[n][j] 表示只有w[n]物品，背包的容量为j时的最大价值
    
15.         for (int l = w[n]; l <= c; l++)
    
16.             m[n][l] = v[n];  //当w[n]<=j 有m[n][j]=v[n]
    
17.         //递规调用求出m[][]其它值，直到求出m[0][c]
    
18.         for(int i = n-1; i >=1; i--)
    
19.         {
    
20.             jMax = Math.min(w[i]-1,c);            
    
21.             for(int k = 0; k <=jMax; k++)
    
22.                 m[i][k] = m[i+1][k];
    
23.                      
    
24.             for(int h = w[i]; h <= c; h++)
    
25.                 m[i][h] = Math.max(m[i+1][h],m[i+1][h-w[i]]+v[i]);
    
26.         }
    
27.         m[0][c] = m[1][c];
    
28.         if(c >= w[0])
    
29.             m[0][c] = Math.max(m[0][c],m[1][c-w[0]]+v[0]);
    
30.         System.out.println("bestw ="+m[0][c]);
    
31.     }
    
32.          
    
33.     public static void traceback(int[][] m, int[] w, int c, int[] x)
    
34.     {// 根据最优值求出最优解
    
35.         int n = w.length-1;
    
36.         for(int i = 0; i< n;i++)
    
37.             if(m[i][c] == m[i+1][c])
    
38.                 x[i] = 0;
    
39.             else{
    
40.                 x[i] = 1;
    
41.                 c -= w[i];
    
42.             }
    
43.         x[n] = (m[n][c]>0)?1:0;
    
44.     }
    
45.     public static void main(String[] args)
    
46.     {
    
47.         //测试
    
48.         int[] ww = {2,2,6,5,4};
    
49.         int[] vv = {6,3,5,4,6};
    
50.         int[][] mm = new int[11][11];
    
51.         knapsack(vv,ww,10,mm);
    
52.         int[] xx =new int[ww.length];
    
53.         traceback(mm,ww,10,xx);
    
54.         for(int i = 0;i< xx.length;i++)
    
55.             System.out.println(xx[i]);
    
56.     }
    
57. }

复制代码

运行结果： C:java>java Knapsack
bestw =15
1
1
0
0
1
  

  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/11/6/000325843.zip