DP 之 01 背包

背包问题

    有很多物体，重量不同、价值不同，以及一个容量有限的背包，选择一些物品装到背包中，问怎么装才能是装进背包的物品总价值最大     根据限定条件不同，可以将背包问题分为很多种，常见的有下面两种： 如果每个物体可以切分，称为一般背包问题，用贪心法求最优解。如果每个物体不可分割，称为 0/1 背包问题。这种问题无法用贪心法求得最优解。

0/1 背包问题

    给定 n 种物品和一个背包，物品 i 的重量是 wi、价值为 vi，背包的总容量为 C。在装入背包的物品时对每种物品 i 只有两种选择，即装入背包和不装入背包（称为 0/1 背包）。如何选择装入背包的物品，使得装入背包中的物品总价值最大？

DP求解 0/1 背包

    后面的描述都基于这个例子：有 4 个物品，其重量为分别是：2、3、6、5，价值分别为：6、3、5、4，背包容量为 9     引进一个 (n+1)*(C+1) 的二维表 dp[][]，可以把每个 dp[i][j] 都看成一个背包，dp[i][j] 表示把前 i 个物品装入容量为 j 的背包中获得的最大价值，i 是纵坐标，j 是横坐标。     填表按照只装第 1 个物品、只装前两个物品、……的顺序，直到装完，如下图所示。这是从小问题扩展到大问题的过程     步骤 1：只装第 1 个物品     由于物品 1 的重量是 2，所以背包容量小于 2 的都放不进去，得 dp[1][0] = dp[1][1] = 0；物品 1 的重量等于背包容量，装进去，背包价值等于物品 1 的价值，dp[1][2] = 6；容量大于 2 的背包，多余的容量暂时用不到，所以价值和容量 2 的背包一样，如下图所示     步骤 2：只装前两个物品     如果物品 2 的重量比背包容量大，那么不装物品 2，情况和只装第 1 个物品一样     下面填 dp[2][3]。物品 2 的重量等于背包容量，那么可以装物品 2，也可以不装：

    (1) 如果装物品 2 (重量是 3），那么相当于只把物品 1 装到（容量减 3）的背包中，即舍弃一定量（腾出能容纳当前物品的空间）的物品来装载当前物品。如下图所示：

    (2)如果不装物品 2，那么相当于只把物品 1 装到背包中，如下图所示：

    后续步骤：继续以上的过程，最后得到下图（图中箭头是几个例子）

    最后答案是 dp[4][9]，即把 4 个物品装到容量 为 9 的背包，最大价值是 11     其 算法复杂度 是 O(nC)

输出 0/1 背包方案     现在回头看具体装了哪些物品，需要倒过来观察：     dp[4][9] = max{ dp[3][4] + 4, dp[3][9] } = dp[3][9]，说明没有装物品 4，用 X4 = 0 表示；     dp[3][9] = max{ dp[2][3] + 5, dp[2][9] } = dp[2][3] + 5 =11，说明装了物品 3，X3 = 1 表示；     dp[2][3] = max{ dp[1][0] + 3, dp[1][3] } = dp[1][3]，说明没有装物品 2，X2 = 0；     dp[1][3] = max{ dp[0][1] + 6, dp[0][3] } = dp[0][1] + 6 = 6，说明装了物品 1，X1 = 1。     下图的实线箭头指出了方案的路径：

例题

代码如下（Java）`

import java.util.*; public class Main{ class BONE{ //相当于结构体，记录每个骨头的价值和体积 int val; int vol; } int N,V; int[][] dp = new int[1011][1011]; int[] dp2 = new int[1011]; //替换 int[][] dp BONE bone[] = new BONE[1011]; public Main(){ for(int i=0; i<bone.length; i++){ bone[i] = new BONE(); //初始化类数组 } } int ans(){ for(int i=0; i<1011; i++) //每次重置数组元素的值 Arrays.fill(dp[i],0); for(int i=1; i<=N; i++) for(int j=0; j<=V; j++){ if(bone[i].vol > j) //第 i 个物品太大，装不了 dp[i][j] = dp[i-1][j]; else //第 i 个物品可以装 dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-bone[i].vol]+bone[i].val); //见注脚1 } return dp[N][V]; } int ans2(){ //见注脚2 Arrays.fill(dp2,0); for(int i=1; i<=N; i++) for(int j=V; j>=bone[i].vol; j--){ //反过来循环 dp2[j] = Math.max(dp2[j], dp2[j-bone[i].vol]+bone[i].val); } return dp2[V]; } public static void main(String[] args) { Main m = new Main(); Scanner sc = new Scanner(System.in); int n; n = sc.nextInt(); while (n-->0){ m.N = sc.nextInt(); m.V = sc.nextInt(); for(int i=1; i<=m.N; i++) m.bone[i].val = sc.nextInt(); for(int i=1; i<=m.N; i++) m.bone[i].vol = sc.nextInt(); System.out.println(m.ans()); System.out.println(m.ans2()); } } }

^{1 2}

---

该语句的理解：将 不装该物品时的背包价值 与 舍弃一定量物品（即腾出能容纳当前物品的空间）来装载当前物品后的背包价值 作比较 ↩︎

此方法是利用滚动数组：把 dp[][] 变成一维的 dp[]，以节省空间。观察上面的二维表 dp[][] 可以发现，每一行是从上面一行算出来的，只与上面一行有关系，与更前面的行都没有关系。那么用新的一行覆盖原来的一行就可以了 ↩︎