DP 之 0/1 背包

背包问题

    有很多物体，重量不同、价值不同，以及一个容量有限的背包，选择一些物品装到背包中，问怎么装才能是装进背包的物品总价值最大
    根据限定条件不同，可以将背包问题分为很多种，常见的有下面两种：

1. 如果每个物体可以切分，称为一般背包问题，用贪心法求最优解。
2. 如果每个物体不可分割，称为 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

---

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

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