首先给出01背包问题定义：

设有一背包，容量为V, 有N个物体, 每个物体体积V[i], 价值W[i]，求该背包所能带走物体的最大价值。

这是一个动态规划题。解题思路是根据最后一个物体放还是不放，将问题递归分为两类。"一子天下动"，这是很常见的思路。

方程：$F[N][V] = max{F[N-1][V], F[N-1][V-V[N]] + W[N]}$。

关键在于F[N][V]的含义，理解透彻后，问题迎刃而解。

下面给出编程实现，复杂度由高到低（为简单起见，设V[i] = W[i]）。

方程是递归的，下面给出递归解法：

1     public static int maxValue(int[] weight, int sum, int i, int limit ,int n){ 2         if (i < 0) { 3             return sum; 4         } 5         int s1 = 0, s2 = 0; 6         if (sum + weight[i] <= limit) { 7             s1 = maxValue(weight, sum + weight[i], i - 1, limit, n); 8         } 9         s2 = maxValue(weight, sum, i - 1, limit, n);10         if (s1 >= s2) {11             return s1;12         } else {13             return s2;14         }15     }

递归算法复杂度$O(2^N)$， 太高了。怎么降低呢？问题空间大小不过V*N，我们对问题空间进行迭代求解，自然就得出答案。

这时时间复杂度降为O(N*V), 空间复杂度也是为O(N*V)。

1 public static int maxValueNonRecursion(int[] weight, int limit){ 2         int n = weight.length; 3         int[][] result = new int[n][limit+1]; 4         for (int i = 0; i < n; i++){ 5             for (int j = 0; j < limit+1; j++) { 6                 if (i == 0){ 7                     if (j >= weight[i]){ 8                         result[i][j] = weight[i]; 9                     }10                 }else {11                     if (j < weight[i]) {12                         result[i][j] = result[i - 1][j];13                     } else {14                         result[i][j] = Math.max(result[i - 1][j], result[i - 1][j - weight[i]] + weight[i]);15                     }16                 }17             }18         }19         return result[n-1][limit];20     }

时间复杂度已降到极限（还可进行细节优化，不过数量级不变），空间复杂度还可降低，因为只保存前后一层的结果，空间复杂度可降至O(V)。为什么不是O(N）？ 深入理解迭代过程后，自然就明白了。

注意第二层循环为什么是逆序，这是故意的。因为不逆序，改变新值时，老值也会变化。而逆序后，则完美的解决了这一问题。

1     public static int maxValueNonRecursionSaveSpace(int[] weight, int limit){ 2         int n = weight.length; 3         int[] result = new int[limit+1]; 4         for (int i = 0; i < n; i++) { 5             for (int j = limit; j >= 0; j--) { 6                 if (j >= weight[i]){ 7                     result[j] = Math.max(result[j], result[j-weight[i]] + weight[i]); 8                 } 9             }10         }11         return result[limit];12     }

这时，时间复杂度O(V*N), 空间复杂度O(V)。二者都降无可降，这是可以接受的。

 

01背包应用举例：

将数组元素分成两堆，使它们元素和尽可能相等，可化为01背包。