Fork me on GitHub

数据结构与算法-8-动态规划-背包系列

原文:https://mp.weixin.qq.com/s/RXfnhSpVBmVneQjDSUSAVQ

一、背包系列

1、01背包

给你一个可装载重量为W的背包和N个物品,每个物品有重量和价值两个属性。其中第i个物品的重量为wt[i],价值为val[i],现在让你用这个背包装物品,最多能装的价值是多少?

举个简单的例子,输入如下:

N = 3, W = 4
wt = [2, 1, 3]
val = [4, 2, 3]

算法返回 6,选择前两件物品装进背包,总重量 3 小于W,可以获得最大价值 6。

思考:

题目中的物品不可以分割,要么装进包里,要么不装,不能说切成两块装一半。

第一步:

状态:「背包的容量」和「可选择的物品」
选择:「装进背包」或者「不装进背包」
1
2
3
4
for 状态1 in 状态1的所有取值:
for 状态2 in 状态2的所有取值:
for ...
dp[状态1][状态2][...] = 择优(选择1,选择2...)

第二步:dp数组的定义

明确问题有什么「状态」,现在需要用dp数组把状态表示出来。

「状态」,有两个,也就是说我们需要一个二维dp数组,一维表示可选择的物品,一维表示背包的容量。

dp[i][w]的定义如下:对于前i个物品,当前背包的容量为w,这种情况下可以装的最大价值是dp[i][w]。

比如说,如果 dp[3][5] = 6,其含义为:对于给定的一系列物品中,若只对前 3 个物品进行选择,当背包容量为 5 时,最多可以装下的价值为 6。

bad case:
dp[0][..] = dp[..][0] = 0,因为没有物品或者背包没有空间的时候,能装的最大价值就是 0。

答案就是dp[N][W]

1
2
3
4
5
6
7
8
9
10
11
int dp[N+1][W+1]
dp[0][..] = 0
dp[..][0] = 0

for i in [1..N]:
for w in [1..W]:
dp[i][w] = max(
把物品 i 装进背包,
不把物品 i 装进背包
)
return dp[N][W]

第三步:根据「选择」,思考状态转移的逻辑

dp[i][w]表示:对于前i个物品,当前背包的容量为w时,这种情况下可以装下的最大价值是dp[i][w]。

如果你没有把这第i个物品装入背包,那么很显然,最大价值dp[i][w]应该等于dp[i-1][w]。不装的时候,那就继承之前的结果。

如果你把这第i个物品装入了背包,那么dp[i][w]应该等于dp[i-1][w-wt[i-1]] + val[i-1]。

ps:

由于i是从 1 开始的,所以对val和wt的取值是i-1。

dp[i-1][w-wt[i-1]]:你如果想装第i个物品,你怎么计算这时候的最大价值?换句话说,在装第i个物品的前提下,背包能装的最大价值是多少?

寻求剩余重量w-wt[i-1]限制下能装的最大价值,加上第i个物品的价值val[i-1],这就是装第i个物品的前提下,背包可以装的最大价值。
1
2
3
4
5
6
7
for i in [1..N]:
for w in [1..W]:
dp[i][w] = max(
dp[i-1][w],
dp[i-1][w - wt[i-1]] + val[i-1]
)
return dp[N][W]

c++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int knapsack(int W, int N, vector<int>& wt, vector<int>& val) {
// vector 全填入 0,base case 已初始化
vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= N; i++) {
for (int w = 1; w <= W; w++) {
if (w - wt[i-1] < 0) {
// 当前背包容量装不下,只能选择不装入背包
dp[i][w] = dp[i - 1][w];
} else {
// 装入或者不装入背包,择优
dp[i][w] = max(dp[i - 1][w - wt[i-1]] + val[i-1],
dp[i - 1][w]);
}
}
}

return dp[N][W];
}

python:

1
2
3
4
5
6
7
8
9
10
def knapsack(W,N,wt,val):
dp=[[0]*(W+1) for i in range(N+1)]
for i in range(1,N+1):
for j in range(1,W+1):
if j-wt[i-1] < 0:
dp[i][j]=dp[i-1][j]
else:
dp[i][j]=max(dp[i-1][j-wt[i-1]]+val[i-1],dp[i-1][j])
# print(dp)
return dp[N][W]

2、01背包变体

416. 分割等和子集

链接:https://leetcode-cn.com/problems/partition-equal-subset-sum/

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

注意:

每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.

思考:

给你一个可装载重量为W的背包和N个物品,每个物品有重量和价值两个属性。其中第i个物品的重量为wt[i],价值为val[i],现在让你用这个背包装物品,最多能装的价值是多少?

可以先对集合求和,得出sum,把问题转化为背包问题:给一个可装载重量为sum/2的背包和N个物品,每个物品的重量为nums[i]。现在让你装物品,是否存在一种装法,能够恰好将背包装满?

第一步:

状态:「背包的容量」和「可选择的物品」
选择:「装进背包」或者「不装进背包」

第二步:dp数组的定义

dp[i][j] = x表示,对于前i个物品,当前背包的容量为j时,若x为true,则说明可以恰好将背包装满,若x为false,则说明不能恰好将背包装满。

比如说,如果dp[4][9] = true,其含义为:对于容量为 9 的背包,若只是用前 4 个物品,可以有一种方法把背包恰好装满。

或者说对于本题,含义是对于给定的集合中,若只对前 4 个数字进行选择,存在一个子集的和可以恰好凑出 9。

根据这个定义,我们想求的最终答案就是dp[N][sum/2],base case 就是dp[..][0] = true和dp[0][..] = false,因为背包没有空间的时候,就相当于装满了,而当没有物品可选择的时候,肯定没办法装满背包。

第三步:根据「选择」,思考状态转移的逻辑

根据「选择」对dp[i][j]得到以下状态转移:

如果不把nums[i]算入子集,或者说你不把这第i个物品装入背包,那么是否能够恰好装满背包,取决于上一个状态dp[i-1][j],继承之前的结果。

如果把nums[i]算入子集,或者说你把这第i个物品装入了背包,那么是否能够恰好装满背包,取决于状态dp[i - 1][j-nums[i-1]]。

首先,由于i是从 1 开始的,而数组索引是从 0 开始的,所以第i个物品的重量应该是nums[i-1],这一点不要搞混。

dp[i - 1][j-nums[i-1]]也很好理解:你如果装了第i个物品,就要看背包的剩余重量j - nums[i-1]限制下是否能够被恰好装满。

换句话说,如果j - nums[i-1]的重量可以被恰好装满,那么只要把第i个物品装进去,也可恰好装满j的重量;否则的话,重量j肯定是装不满的。

c++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
bool canPartition(vector<int>& nums) {
int sum = 0;
for (int num : nums) sum += num;
// 和为奇数时,不可能划分成两个和相等的集合
if (sum % 2 != 0) return false;
int n = nums.size();
sum = sum / 2;
vector<vector<bool>>
dp(n + 1, vector<bool>(sum + 1, false));
// base case
for (int i = 0; i <= n; i++)
dp[i][0] = true;

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
if (j - nums[i - 1] < 0) {
// 背包容量不足,不能装入第 i 个物品
dp[i][j] = dp[i - 1][j];
} else {
// 装入或不装入背包
dp[i][j] = dp[i - 1][j] | dp[i - 1][j-nums[i-1]];
}
}
}
return dp[n][sum];
}

python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def canPartition(self, nums: List[int]) -> bool:
sum=0
for i in nums:
sum+=i
if sum %2 != 0:
return False
n=len(nums)
sum=sum//2
dp=[[False]*(sum+1) for i in range(n+1)]
# print(dp)
for i in range(n+1):
dp[i][0]=True
for i in range(1,n+1):
for j in range(1,sum+1):
if j-nums[i-1]<0:
dp[i][j]=dp[i-1][j]
else:
dp[i][j]=dp[i-1][j] or dp[i-1][j-nums[i-1]]
# dp[i][j]=dp[i-1][j] | dp[i-1][j-nums[i-1]]
return dp[n][sum]

状态压缩:

注意:

dp[i][j]都是通过上一行dp[i-1][..]转移过来的,之前的数据都不会再使用了。
dp[j]其实就相当于dp[i-1][j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool canPartition(vector<int>& nums) {
int sum = 0, n = nums.size();
for (int num : nums) sum += num;
if (sum % 2 != 0) return false;
sum = sum / 2;
vector<bool> dp(sum + 1, false);
// base case
dp[0] = true;

for (int i = 0; i < n; i++)
for (int j = sum; j >= 0; j--)
if (j - nums[i] >= 0)
dp[j] = dp[j] || dp[j - nums[i]];

return dp[sum];
}

3、完全背包

518. 零钱兑换 II

链接:https://leetcode-cn.com/problems/coin-change-2/

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 

示例 1:

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:

输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
示例 3:

输入: amount = 10, coins = [10] 
输出: 1


注意:

你可以假设:

0 <= amount (总金额) <= 5000
1 <= coin (硬币面额) <= 5000
硬币种类不超过 500 种
结果符合 32 位符号整数

思考:

有一个背包,最大容量为amount,有一系列物品coins,每个物品的重量为coins[i],每个物品的数量无限。请问有多少种方法,能够把背包恰好装满?

和01背包最大的区别就是,每个物品的数量是无限的,这也就是传说中的「完全背包问题」

第一步:

状态:「背包的容量」和「可选择的物品」
选择:「装进背包」或者「不装进背包」
1
2
3
4
for 状态1 in 状态1的所有取值:
for 状态2 in 状态2的所有取值:
for ...
dp[状态1][状态2][...] = 计算(选择1,选择2...)

第二步:dp数组的定义

dp[i][j]的定义如下:

若只使用前i个物品,当背包容量为j时,有dp[i][j]种方法可以装满背包。
即只使用coins中的前i个硬币的面值,若想凑出金额j,有dp[i][j]种凑法。

base case 为dp[0][..] = 0, dp[..][0] = 1。因为如果不使用任何硬币面值,就无法凑出任何金额;如果凑出的目标金额为 0,那么“无为而治”就是唯一的一种凑法。

答案就是dp[N][amount],其中N为coins数组的大小。

1
2
3
4
5
6
7
8
9
int dp[N+1][amount+1]
dp[0][..] = 0
dp[..][0] = 1

for i in [1..N]:
for j in [1..amount]:
把物品 i 装进背包,
不把物品 i 装进背包
return dp[N][amount]

第三步:根据「选择」,思考状态转移的逻辑

特殊点:在于物品的数量是无限的

如果你不把这第i个物品装入背包,也就是说你不使用coins[i]这个面值的硬币,那么凑出面额j的方法数dp[i][j]应该等于dp[i-1][j],继承之前的结果。

如果你把这第i个物品装入了背包,也就是说你使用coins[i]这个面值的硬币,那么dp[i][j]应该等于dp[i][j-coins[i-1]]。

首先由于i是从 1 开始的,所以coins的索引是i-1时表示第i个硬币的面值。

总结:

状态:硬币,金额
选择:当前硬币选或者不选

dp数组含义:dp[i][j]表示前i个硬币可以达到j金额的组合数

状态转移方程:dp[i][j]=dp[i−1][j]+dp[i][j−coins[i−1]]

注意:就是不选和选相加,选时的硬币下标仍为i,因为硬币个数无限,这个硬币上次仍然可以选;
     完全背包和01背包的唯一不同之处;

java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int change(int amount, int[] coins) {
int n = coins.length;
int[][] dp = amount int[n + 1][amount + 1];
// base case
for (int i = 0; i <= n; i++)
dp[i][0] = 1;

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= amount; j++)
if (j - coins[i-1] >= 0)
dp[i][j] = dp[i - 1][j]
+ dp[i][j - coins[i-1]];
else
dp[i][j] = dp[i - 1][j];
}
return dp[n][amount];
}

1
2
3
4
5
6
7
8
9
10
11
int change(int amount, int[] coins) {
int n = coins.length;
int[] dp = new int[amount + 1];
dp[0] = 1; // base case
for (int i = 0; i < n; i++)
for (int j = 1; j <= amount; j++)
if (j - coins[i] >= 0)
dp[j] = dp[j] + dp[j-coins[i]];

return dp[amount];
}

python:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
n=len(coins)
dp=[[0]*(amount+1) for i in range(n+1)]
for i in range(n+1):
dp[i][0]=1
for i in range(1,n+1):
for j in range(1,amount+1):
if j-coins[i-1]>=0:
dp[i][j]=dp[i-1][j]+dp[i][j-coins[i-1]]
else:
dp[i][j]=dp[i-1][j]
return dp[n][amount]
支持,让我的文章更加优秀!