背包问题

发表于 | 分类于

0-1背包问题

描述：有N件物品和一个容量为V的背包。第i件物品的费用是w[i]，价值是v[i]。求解将哪些物品装入背包可使价值总和最大。

特点是：每种物品仅有一件，可以选择放或不放。

思路：对于前i件物品放入容量为j的背包中这个问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为j的背包中”，价值为f[i-1][j]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为j-v[i]的背包中”，此时能获得的最大价值就是f[i-1][j-v[i]]再加上通过放入第i件物品获得的价值w[i]。

1
dp[i][j] = max(f[i - 1][j],f[i - 1][j - w[i]] + v[i])

例子：5个物品，（重量，价值）分别为：（5，12），（4，3），（7，10），（2，3），（6，6）:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Main {
    public static void main(String[] args) {
        int[] v = new int[]{12, 3, 10, 3, 6};
        int[] w = new int[]{5, 4, 7, 2, 6};
        int[][] dp = new int[5][16];
      	//初始化第一行
        for (int j = 0; j <= 15; j++) {
            dp[0][j] = w[0] <= j ? v[0] : 0;
        }
        for (int i = 1; i < 5; i++) {
            for (int j = 1; j <= 15; j++) {
                if (j - w[i] >= 0) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        System.out.println(dp[4][15]);
    }
}

拓展：对于空间的优化？

采用滚动数组的思想进行降维处理：

将i视作数组的更新轮数

dp[i][v]是由dp[i-1][v]和dp[i-1][j-v[i]]两个子问题递推而来，能否保证在推dp[i][j]时（也即在第i次主循环中推dp[j]时）能够得到dp[i-1][j]和dp[i-1][j-v[i]]的值呢？事实上，这要求在每次主循环中我们以j=V..0的顺序推dp[j]，这样才能保证推dp[j]时dp[j-v[i]]保存的是状态dp[i-1][j-v[i]]的值。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了dp[i][j]由dp[i][j-v[i]]推知，与本题意不符。

伪代码：

1
2
3
4
5
for i=1..N:

	for j=V..0:

		dp[j]=max{dp[j],f[j-v[i]]+w[i]};

再拓展：如果要求放满怎么办？

那么在初始化时除了dp[0]为0,其它dp、[1..V]均设为负无穷，这样就可以保证最终得到的dp[N]是一种恰好装满背包的最优解。

可以这样理解：初始化的dp数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是负无穷了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。

完全背包问题

描述：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

先说最基本的算法：

1
dp[i][j]=max{ dp[i-1][j-k*c[i]]+k*w[i]  |  0<=k*c[i]<=v}

改进思路1：转化为01背包问题，因为物品都有无限件可用,那么没见物品最多放置V/v[i]个，我们可以把物品列表补全到这么多个然后用0-1背包的方法来解决（这里就不给代码啦）

改进思路2：在完全背包中，每种物品可选无限件，在求解加选第i种物品带来的收益f[i][v]时，在状态f[i][v-c[i]]中已经尽可能多的放入物品i了，此时在f[i][v-c[i]]的基础上，我们可以再次放入一件物品i，此时也是在不超过背包容量的基础下，尽可能多的放入物品i。
完全背包的方程：

1
dp[i][j] = max(f[i - 1][j],f[i][j - w[i]] + v[i]);

可以同样采用滚动数组的方法进行降维处理：

降维后的状态转移方程为：

1
2
dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
//这里遍历j的时候就需要从0到v了，相当于一件一件地加第i件物品

多重背包问题

描述：有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

直接上没有优化的状态转移公式吧

1
dp[i][j] = max{dp[i − 1][j − k * w[i]] + k * v[i] (0 ≤ k ≤ n[i]) }