跳到主要内容

算法基础 1

· 阅读需 4 分钟

https://oi-wiki.org/dp/knapsack/#0-1-背包

0-1 背包问题是指有一个固定大小、能够携带重量为 W 的背包，以及一组有价值和重量的物品，需要决定将哪些物品放入背包中，以便在不超过背包容量的前提下，让背包中的总价值最大。

状态转移方程​

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

其中 dp[i][j] 表示前 i 件物品放入容量为 j 的背包可以获得的最大价值，w[i] 和 v[i] 分别表示第 i 件物品的重量和价值。

优化​

将二维数组压缩为一维数组，即 dp[j] = max(dp[j], dp[j - w[i]] + v[i])。这是因为当前状态只与上一个状态有关，因此可以使用滚动数组来优化空间复杂度。

例题​

LeetCode 416​

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

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

答：转移方程为 dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]] ，其中 dp[i][j] 表示前 i 个数组成的数组，其某个子集的和是否等于 j ，再配合滚动数组优化变为 1d DP。

核心代码：

dp = [False] * (half_s + 1)
dp[0] = True
for num in nums:
    for j in range(half_s, num - 1, -1):
        dp[j] = dp[j] or dp[j - num]

LeetCode 474​

https://leetcode.com/problems/ones-and-zeroes/

题意：给定一个字符串数组，每个字符串只包含 0 和 1。你有 m 个 0 和 n 个 1，问最多能选出多少个字符串，使得这些字符串中的 0 的个数不超过 m，1 的个数不超过 n。

答：令 dp[i][j][k] 表示前 i 个字符串中元素最多的子集，该子集的元素至多有 j 个 0 和 k 个 1。最终的解为 dp[len(strs) - 1][m][n]。

转移方程为 dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-f[strs[i]]][k-g[str[i]]]+1)，其中 f 和 g 代表 0 和 1 的个数。可以通过滚动数组优化为二维 DP。

核心代码：

dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
for i in range(N):
    for j in range(m, f[i] - 1, -1):
        for k in range(n, g[i] - 1, -1):
            dp[j][k] = max(dp[j][k], dp[j - f[i]][k - g[i]] + 1)
return dp[-1][-1]

LeetCode 1049​

https://leetcode.com/problems/last-stone-weight-ii/

给定一个正整数数组 stones，其中每个元素表示一块石头的重量。现在你需要将这些石头分成两组，使得每组石头的重量之和尽量接近。求这个最小的差值。

答：可以将问题转化求两组石头重量和之差的最小值。

令dp[i][j]表示前i块石头中是否存在子集，其重量之和为j。状态转移方程为dp[i][j] = dp[i-1][j] or dp[i-1][j-w[i]]。最终的解为sum(stones) - j * 2, if dp[len(stones) - 1][j] == True。

核心代码：

for stone in stones:
    for j in range(s_half, stone - 1, -1):
        dp[j] = dp[j] or dp[j - stone]
for j in range(s_half, -1, -1):
    if dp[j]:
        return s - j - j