背包问题算法的JAVA实现

eimhee

问题描述：
设U = {u1,u2,u3,......ui}(一共有amount数量的物品)是一组准备放入背包中的物品.设背包的容量为size.
定义每个物品都具有两个属性weight和value.
我们要解决的问题就是计算在所选取的物品总重量不超过背包容量size的前提下使所选的物品总价值最大.


一句话，让你的有限背包，装上最终总价值最高的物品。


注意，代码里面我加上了打印语句，可以用来查看算法的过程

<div class="highlighter">

• import java.util.Arrays;
  
• <span />
  
• <span />/**
  
•  * 背包问题
  
•  * @author 赵学庆 java2000.net
  
•  *
  
•  */<span />
  
• public class T {
  
•   /**
  
•    * @param value 价值
  
•    * @param weight 重量
  
•    * @param capicity 背包容量
  
•    * @param m 表示只有w,w[i+1]...w[n]这些物品时,背包容量为j时的最大价值
  
•    */<span />
  
•   public static void knapsack(int[] value, int[] weight, int capicity, int[][] m) {
  
•     // 数量<span />
  
•     int n = value.length - 1;
  
•     // 最后一个重量-1和容量的更小的一个<span />
  
•     int jMax = Math.min(weight[n] - 1, capicity);
  
•     // 将最后一个数组的前部分清空。<span />
  
•     for (int j = 0; j <= jMax; j++)
  
•       m[n][j] = 0; // 当w[n]>j 有 m[n][j]=0<span />
  
•     showArray(m);
  
•     // 后半部分设置为此物品的价值<span />
  
•     // m[n][j] 表示只有w[n]物品，背包的容量为j时的最大价值<span />
  
•     for (int j = weight[n]; j <= capicity; j++)
  
•       m[n][j] = value[n]; // 当w[n]<=j 有m[n][j]=v[n]<span />
  
•     showArray(m);
  
•     // 递规调用求出m[][]其它值，直到求出m[0][c]<span />
  
•     for (int i = n - 1; i >= 1; i--) {
  
•       jMax = Math.min(weight - 1, capicity);
  
•       System.out.println(jMax);
  
•       for (int k = 0; k <= jMax; k++)
  
•         m[k] = m[i + 1][k];
  
•       showArray(m);
  
•       for (int h = weight; h <= capicity; h++) {
  
•         System.out.println(m[i+1][h]+" / "+ m[i + 1][h - weight]+" + " +value+"("+h+","+weight+","+value+")");
  
•         m[h] = Math.max(m[i + 1][h], m[i + 1][h - weight] + value);
  
•       }
  
•       showArray(m);
  
•     }
  
•     m[0][capicity] = m[1][capicity];
  
•     if (capicity >= weight[0])
  
•       m[0][capicity] = Math.max(m[0][capicity], m[1][capicity - weight[0]] + value[0]);
  
•     System.out.println("bestw =" + m[0][capicity]);
  
•   }
  
• <span />
  
•   public static void showArray(int[][] m) {
  
•     for (int[] a : m) {
  
•       System.out.println(Arrays.toString(a));
  
•     }
  
•     System.out.println("-------------------------------------------");
  
•   }
  
• <span />
  
•   public static void traceback(int[][] m, int[] w, int c, int[] x) {// 根据最优值求出最优解<span />
  
•     int n = w.length - 1;
  
•     for (int i = 0; i < n; i++)
  
•       if (m[c] == m[i + 1][c])
  
•         x = 0;
  
•       else {
  
•         x = 1;
  
•         c -= w;
  
•       }
  
•     x[n] = (m[n][c] > 0) ? 1 : 0;
  
•   }
  
• <span />
  
•   public static void main(String[] args) {
  
•     // 测试<span />
  
•     int[] ww = { 8,5,4,3 };
  
•     int[] vv = { 10,7,5,4 };
  
•     int[][] mm = new int[4][13];
  
•     knapsack(vv, ww, 12, mm);
  
•     int[] xx = new int[ww.length];
  
•     traceback(mm, ww, 12, xx);
  
•     for (int i = 0; i < xx.length; i++)
  
•       System.out.println(xx);
  
•   }
  
• }