书成

再这样堕落下去就给我去死啊你这混蛋！！！

0%

背包问题

发表于 更新于 分类于

部分背包问题

 部分背包问题即装入背包的物品可分割，可以用简单的贪心算法解决，物品平均价值由高到低排序，依次放入背包，直到放不下。

 例如：有一堆金粉，银粉，铜粉和铁粉，用一个固定大小的袋子去装，只要从平均价值最大的金粉开始装，装完后装下一堆平均价值最大的物品，直到袋子装满为止即可。

01背包问题

问题描述

 有N件物品，第 i 件物品重Ci，价值Wi，你有一个能装重量V的背包，每件物品只有一个，你需要装入哪些物品才能使背包内的价值总和最大？

动态规划公式

 定义dp[i, v]表示将前 i 件物品放入容量为 v 的背包可以获得最大价值总和，那么在这个情况下，有两种可能，要么第 i 件物品放入了背包内， 要么第 i 件物品没有放入背包内。

 如果第 i 件物品没有放入背包内，相当于dp[i, v] = dp[i - 1, v]，即将前面 i - 1件物品放入容量为v的背包中的最大价值总和。

 如果第 i 件物品放入了背包内，相当于dp[i, v] = dp[i - 1, v - Ci] + Wi，因为第 i 件物品放入了背包，所以相当于前面 i - 1 件物品占用v - Ci的空间的最大价值总和再加上第 i 件物品的价值。

 但是两种可能只能选择一种，价值最大的那种，所以01背包的递推公式为：dp[i, v] = max{dp[i - 1, v], dp[i - 1, v - Ci] + Wi}

解法与优化

 既然已经得到了递推公式，根据递推公式不断计算，最终算到dp[N, V]就是问题的答案了，可以创建一个二维数组计算。

1
2
3
4
5
6
7
8
9
public int bagProblem(int[] C, int[] W, int V){
	int[][] dp = new dp[C.length + 1][V + 1];
	for(int i = 1; i <= C.length; i++){
    	for(int j = C[i]; j <= V; j++){
        	dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - C[i]] + W[i]);
    	}
	}   
    return dp[C.length][[V];
}

 从代码中不难看出，二维数组在计算过程中是逐行计算的，并且第 i 行的数据只依赖于第 i - 1行的数据，因此前面已经计算过的行其实已经无用了，可以删掉它们优化空间。最佳的优化下，可以只使用一维数组来计算。
 只用一维数组来计算的关键点在于，每一行数据在计算的时候，都依赖前面已经计算的元素，依赖于前面的 j - C[i]位置上的元素，如果依旧从前到后依次计算，拿到的这个位置的元素的值就是错的。所以这个时候需要从后到前计算，这样就能保证每次取 j - C[i]位置上的元素，都是上一次计算的结果。

1
2
3
4
5
6
7
8
9
public int bagProblem(int[] C, int[] W, int V){
    int[] dp = new dp[V + 1];
    for(int i = 1; i <= C.length; i++){
        for(int j = V; j >= C[i]; j--){
            dp[j] = Math.max(dp[j], dp[j - C[i] + W[i]);
        }
    }
    return dp[V];                                 
}

 另外，在这个代码中，可以抽象出处理一件01背包问题的代码作为一个函数调用：

1
2
3
4
5
6
7
8
9
10
11
public void zeroOneBag(int w, int c, int V, int[] dp){
    for(int j = V; j >= c; j--)
    	dp[j] = Math.max(dp[j], dp[j - c] + w);
}

public int bagProblem(int[] C, int[] W, int V){
    int[] dp = new dp[V + 1];
    for(int i = 1; i <= C.length; i++)
    	zeroOneBag(W[i], C[i], V, dp);
    return dp[V];
}

完全背包问题

问题描述

 完全背包问题与01背包问题唯一的区别在于，每一种物品都有无限多个，可以拿0个，1个，任意个。很显然，直觉上看，这种情况下问题的复杂性十分高，可能的情况实在太多。

动态规划公式推导

 完全背包问题的递推式如下所示：

  dp[i, j] = max( dp[i - 1, j - kC[i] ] + k W[i] ) 其中 0 <= k <= V/C[i] (1)

 即利用穷举的方式从不拿第 i 件物品到拿第 i 件物品装满背包都试一遍，看哪一种方案价值更大就选择哪一种方案。对于这种思路，就是将完全背包问题转化为01背包问题来求解，也有一些优化手段，比如如果两件物品 i 与 j 满足 C[i] <= C[j] && W[i] >= W[j]， 那么可以直接不用考虑 j 物品，因为每个物品可以拿无限多个，所以用价值高费用小的 i 替换 j 是显然不亏的。再比如用二进制编码的思想降低复杂度。

 但是，通过完全背包问题的递推式推导，却可以得到一个简单易懂的解决方法：

 完全背包问题递推式可以写成：

  dp[i, j] = max( dp[i - 1, j], dp[i - 1, j - kC[i]] + k W[i] ) 其中 1 <= k <= V/C[i] (2)

 由(1)式可得：

  dp[i, j - C[i]] = max( dp[i - 1, j - C[i] - kC[i]] + k W[i] ) 其中 1 <= k + 1 <= V/C[i]

  dp[i, j - C[i]] = max( dp[i - 1, j - (k + 1)C[i]] + (k + 1) W[i] - W[i] ) 其中 1 <= k + 1 <= V/C[i]

 令 m = k + 1 则可推导出：

  dp[i, j - C[i]] = max( dp[i - 1, j - mC[i]] + m W[i] - W[i] ) 其中 1 <= m<= V/C[i]

 故可以得到：

  dp[i, j - C[i]] + W[i] = max( dp[i - 1, j - mC[i]] + m W[i] ) 其中 1 <= m <= V/C[i] (3)

 将(3)代入(2)中有：

  dp[i, j] = max( dp[i - 1, j], dp[i, j - C[i]] + W[i] )

 最终的这个公式与01背包的递推式相比较只有一处不同，而且由01背包需要逆序求解容易推导出，完全背包问题只需正序求解就能在一维数组下解决问题：

1
2
3
4
5
6
7
8
9
10
11
public void completeBag(int w, int c, int V, int[] dp){
    for(int j = c; j <= V; j++)
    	dp[j] = Math.max(dp[j], dp[j - c] + w);
}

public int bagProblem(int[] C, int[] W, int V){
    int[] dp = new dp[V + 1];
    for(int i = 1; i <= C.length; i++)
    	completeBag(W[i], C[i], V, dp);
    return dp[V];
}

多重背包问题

 多重背包问题就是每个物品能拿的数量是有限数m，这种情况下，如果一个物品的费用与能拿的次数的积大于背包容量，那么可以转化为完全背包问题求解，否则，要转化为01背包问题求解，可以用二进制编码优化时间复杂度。二进制编码优化是指，可以不用从0遍历到m次，可以转为1，2，4，2^(k-1) 与m - 2^k + 1，其中k表示使2^k - 1 < m的最大k值。例如，m = 19，可以转为1， 2， 4， 8， 12，这样从1到19都能用这几个数组合得到，可以优化时间复杂度。
 传入一个数组M表示第i件物品只能拿M[i]次：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void multiBag(int w, int c, int V, int[] dp, int m){
    if(m * c >= V)
        completeBag(w, c, V, dp);
    else{
        int k = 1;
        while(2 * k - 1 < m){
            zeroOneBag(w * k, c * k, V, dp);
            k = 2 * k;
        }
        m = m - k / 2 + 1;
        zeroOneBag(w * m, c * m, V, dp);
    }
}
public int bagProblem(int[] C, int[] W, int V, int[] M){
    int[] dp = new dp[V + 1];
    for(int i = 1; i <= C.length; i++)
    	multiBag(W[i], C[i], V, dp, M[i]);
    return dp[V];
}

 假设每件物品平均能拿K次，多重背包问题在这种情况下时间复杂度为 $O(NVlgK)$ 。多重背包问题其实存在更好的方法可以达到 $O(NV)$ 的时间复杂度。

混合背包问题

 混合背包问题即之前三种背包问题的混合，有的物品最多只能拿1次，有的能拿无限次，有的能拿有限次。

1
2
3
4
5
6
7
8
9
10
11
12
public int bagProblem(int[] C, int[] W, int V, int[] M){
    int[] dp = new dp[V + 1];
    for(int i = 1; i <= C.length; i++){
        if(M[i] == 1)
        	zeroOneBag(w, c, V, dp);
        else if(M[i] == 0) // 表示能拿无限次
        	completeBag(w, c, V, dp);
        else
        	multiBag(w[i], c[i], V, dp, M[i]);
    }
    return dp[V];
}