0. 前言
经典的动态规划题目:背包问题
1. 问题描述
01背包(ZeroOnePack): 有N件物品和一个承重为bear的背包。每种物品均只有一件。第i件物品的重量是weight[i],价值是value[i]。求解将哪些物品装入背包可使价值总和最大。
完全背包(CompletePack): 有N种物品和一个承重为bear的背包,每种物品都有无限件可用。第i种物品的重量是weight[i],价值是value[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包承重,且价值总和最大。
多重背包(MultiplePack): 有N种物品和一个承重为bear的背包。第i种物品最多有amount[i]件可用,每件重量是weight[i],价值是value[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包承重,且价值总和最大。
2. 01背包求解
最基础的背包问题,总体思路就是:选还是不选
设dp[i][j]表示背包装入前i种物品且承重为j时的最大价值,显然,解为dp[weight.length][bear]
初始状态:
显然dp[0][0] = 0,而且第一列和第一行(承重bear为0或不放入物品)也为0
状态转移方程:
对于一个物品,只有两种情况
- 情况一: 第i件不放进去,这时所得价值为:dp[i - 1][j]
- 情况二: 第i件放进去,这时所得价值为:dp[i - 1][j - weight[i]] + value[i]
状态转移方程为:dp[i][j] = max(f[i - 1][j], f[i - 1][j - weight[i]] + value[i]),j >= weight[i]
时间复杂度O(bear * n)
,空间复杂度O(bear * n)
,其中bear为承重,n为物品数。
实例:1
2
3
4// 共5件物品
int[] weight = {2, 2, 6, 5, 4}; // 重量分别为2, 2, 6, 5, 4
int[] value = {6, 3, 5, 4, 6}; // 价值分别为6, 3, 5, 4, 6
int bear = 10; // 承重为10
weight\bear | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | 0 | 0 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
2 | 0 | 0 | 6 | 6 | 9 | 9 | 9 | 9 | 9 | 9 | 9 |
6 | 0 | 0 | 6 | 6 | 9 | 9 | 9 | 9 | 11 | 11 | 11 |
5 | 0 | 0 | 6 | 6 | 9 | 9 | 9 | 10 | 11 | 13 | 14 |
4 | 0 | 0 | 6 | 6 | 9 | 9 | 12 | 12 | 15 | 15 | 15 |
代码如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21/**
* 01背包:要么放,要么不放
* dp[i][j]表示前i种物品且承重为j时的背包最大价值
* @param weight 重量数组
* @param value 价值数组
* @param bear 承重
* @return 最大的价值总和
*/
public static int zeroOnePack(int[] weight, int[] value, int bear) {
int[][] dp = new int[weight.length + 1][bear + 1];
for (int i = 0; i < weight.length; i++) {
for (int j = 0; j < bear; j++) {
if (j + 1 - weight[i] >= 0) { // 此处判断不可少
dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i][j + 1 - weight[i]] + value[i]);
} else {
dp[i + 1][j + 1] = dp[i][j + 1];
}
}
}
return dp[weight.length][bear];
}
2.1 01背包降维
可以降维到一维数组dp[i],表示承重为i时背包的最大价值
初始状态:
dp[i] = 0, 0 <= i <= bear
状态转移方程:dp[i] = max(dp[i],dp[i - weight[i]] + value[i]) (和降维前是类似的)
时间复杂度O(bear * n)
,空间复杂度O(bear)
,其中bear为承重,n为物品数。
注意,由于dp[i]的计算要用到之前dp[i - weight[i]]的值,所以遍历时要从数组后面逆序遍历,代码如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17/**
* 01背包(降维),二维降一维
* dp[i]表示承重为i时的最大价值
* @param weight 重量数组
* @param value 价值数组
* @param bear 承重
* @return 最大的价值总和
*/
public static int zeroOnePack_DR(int[] weight, int[] value, int bear) {
int[] dp = new int[bear + 1];
for (int i = 0; i < weight.length; i++) {
for (int j = bear; j >= weight[i]; j--) { // 注意要遍历要反过来
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
return dp[bear];
}
3. 完全背包求解
完全背包和01背包十分相像, 区别就是完全背包物品有无限件。由之前的选或者不选转变成了选或者不选,选几件。
设dp[i][j]表示背包装入前i种物品且承重为j时的最大价值,显然,解为dp[weight.length][bear]
初始状态:
显然dp[0][0] = 0,而且第一列和第一行(承重bear为0或不放入物品)也为0
状态转移方程:dp[i][j] = max(dp[i - 1][j - k * weight[i]] + k * value[i] | 0 <= k * weight[i] <= v)
这里不给出代码,直接看降维的解法。
完全背包降维
可以降维到一维数组dp[i],表示承重为i时背包的最大价值
初始状态:
dp[i] = 0, 0 <= i <= bear
状态转移方程:dp[i] = max(dp[i],dp[i - weight[i]] + value[i])
时间复杂度O(bear * n)
,空间复杂度O(bear)
,其中bear为承重,n为物品数。
没错,和01背包的降维法几乎一模一样!区别在于完全背包是顺序计算dp数组的,而01背包是逆序计算dp数组的,代码如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19/**
* 完全背包:要么不放,要么放,放几个
* dp[i]表示承重为i时的最大价值
*
* 与01背包的降维解法刚好逆序
* @param weight 重量数组
* @param value 价值数组
* @param bear 承重
* @return 最大的价值总和
*/
public static int completelyKnapsack(int[] weight, int[] value, int bear) {
int[] dp = new int[bear + 1];
for (int i = 0; i < weight.length; i++) {
for (int j = weight[i]; j <= bear; j++) {
dp[j] = Math.max(dp[j - weight[i]] + value[i], dp[j]);
}
}
return dp[bear];
}
4. 多重背包求解
多重背包多了一个限制条件,每个物品规定了可用的次数。
初始状态:
显然dp[0][0] = 0,而且第一列和第一行(承重bear为0或不放入物品)也为0
状态转移方程:dp[i][j] = max(dp[i - 1][j - k * weight[i]] + k * value[i] | 0 <= k * weight[i] <= amount[i])
这里不给出代码,直接看转化为降维01背包
转化为降维01背包
将n种物品拆分得到Σn种,即Σsize[i], 0 =< i < size.length,,这Σn种物品要么放,要么不放,如此将原问题转化为01背包问题,时间复杂度是O(bear * Σn)
降维到一维数组dp[i],表示承重为i时背包的最大价值
初始状态:
dp[i] = 0, 0 <= i <= bear
状态转移方程:dp[i] = max(dp[i],dp[i - weight[i] * k] + k * value[i]),0 <= k <= amount[i]
时间复杂度是O(bear * Σn)
,空间复杂度O(bear)
,代码如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23/**
* 多重背包,
* dp[i]表示承重为i时的最大价值
*
* 将n种物品拆分得到Σn种,即Σsize[i], 0 =< i < size.length
* 将原问题转化为01背包问题,时间复杂度是O(bear * Σn)
* @param weight 重量数组
* @param value 价值数组
* @param amount 数量数组
* @param bear 承重
* @return 最大的价值总和
*/
public static int multipleKnapsack(int[] weight, int[] value, int[] amount, int bear) {
int[] dp = new int[bear + 1];
for (int i = 0; i < weight.length; i++) {
for (int j = bear; j >= weight[i]; j--) {
for (int k = 1; k <= amount[i] && k * weight[i] <= j; k++) {
dp[j] = Math.max(dp[j - k * weight[i]] + k * value[i], dp[j]);
}
}
}
return dp[bear];
}
有一种对上述算法的优化,同样是转化为01背包求解,不同在于拆分的数目,使用二进制的思想,将第i种物品分成若干种物品,每件物品有一个系数,分别为1, 2, 4,···,2^(k - 1),k是满足n - 2^k + 1 > 0的最大整数,例如n = 13,拆分成1,2,4,6四件物品。又有:8 = 2 + 6, 11 = 1 + 4 + 6,根据二进制的性质,0…13都可以有这四件物品组成,于是n件物品,就拆分成至多logn件物品,而不是上述算法的n,将时间复杂度降到O(bear * Σlogn)
本笔记参考了下属文章: