当前位置：首页 > article >正文

代码随想录算法训练营第三十五天|01背包理论基础|卡码网46.携带研究材料|LC416.分割等和子集

article 2025/2/1 7:58:38

01背包理论（二维数组）

对于面试来讲，其实掌握01背包和完全背包已经完全够用了；而完全背包也是01背包稍作变化而来的，所以背包问题的理论基础的重中之重就是01背包，一定要理解透彻；

01背包将背包容量、价值填写在二维表格中，进行动态规划的思路，便于理解，dp[i][j]；

46. 携带研究材料（第六期模拟笔试）

n, bagweight = map(int, input().split())

weight = list(map(int, input().split()))
value = list(map(int, input().split()))

dp = [[0]*(bagweight+1) for _ in range(n)]

for j in range(weight[0], bagweight+1):
    dp[0][j] = value[0]

for i in range(1, n):
    for j in range(bagweight+1):
        if j < weight[i]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])
print(dp[n-1][bagweight])

01背包理论（一维dp数组（滚动数组））

对于背包问题其实状态是可以进行压缩的；

dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);

与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。

46. 携带研究材料（第六期模拟笔试）

n, bagweight = map(int, input().split())

weight = list(map(int, input().split()))
value = list(map(int, input().split()))
# 创建一个动态规划数组dp，初始值为0
dp = [0] * (bagweight+1)
# 初始化do[0]=0，背包容量为0， 价值最大为0
dp[0] = 0
# 先遍历物品，如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品
for i in range(n):
    # 倒序遍历背包容量是为了保证物品i只被放入一次
    for j in range(bagweight, weight[i] - 1, -1):
        dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
print(dp[bagweight])

416. 分割等和子集 - 力扣（LeetCode）

使用01背包的方法，但是需要进行一些判断才能把01背包的问题套到本题上

1、背包的体积为sum / 2

2、背包要放入的商品（集合里的元素）重量为元素的数值，价值也为元素的数值

3、背包如果正好装满，说明找到了总和为 sum / 2 的子集。

4、背包中每一个元素是不可重复放入。

以上分析完，我们就可以套用01背包，来解决这个问题了。

①确定dp数组以及下标的含义

dp[j]表示背包总容量（所能装的总重量）是j，放进物品后，背的最大重量为dp[j]；那么如果背包容量为target， dp[target]就是装满背包之后的重量，所以当 dp[target] == target 的时候，背包就装满了。

②确定递推公式

本题，相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。所以递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

③dp数组如何初始化

本题题目中只包含正整数的非空数组，所以非0下标的元素初始化为0就可以了。

④确定遍历顺序

如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！

⑤举例推导dp数组

dp[j]的数值一定是小于等于j的。如果dp[j] == j 说明，集合中的子集总和正好可以凑成总和j，理解这一点很重要。

用例1，输入[1,5,11,5] 为例，如图：

最后dp[11] == 11，说明可以将这个数组分割成两个子集，使得两个子集的元素和相等。

from typing import List
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total_sum = sum(nums)

        if total_sum % 2 != 0:
            return False

        target_sum = total_sum // 2

        dp = [[False]*(target_sum+1) for _ in range(len(nums)+1)]
        # 初始化第一行（空子集可以得到和为0）
        for i in range(len(nums)+1):
            dp[i][0] = True

        for i in range(1, len(nums)+1):
            for j in range(1,target_sum+1):
                if j < nums[i-1]:
                    # 当前数字大于目标和时，无法使用该数字
                    dp[i][j] = dp[i-1][j]
                else:
                    # 当前数字小于等于目标时，可以选择使用或不使用该数字
                    dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]
        return dp[len(nums)][target_sum]


if __name__ == '__main__':
    nums = [1,5,11,5]
    res = Solution().canPartition(nums)
    print(res)

查看全文

http://www.kler.cn/a/441105.html