【刷题DAY41】背包, 416.md

发表于 | 分类于

01背包-2维

  • https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html

  • 可以理解

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    # 1.定义dp数组，明确dp[i][j]的含义：
    # 从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大为 dp[i][j]。
    # 2.确定转移公式，
    # dp[i][j] 从dp[i-1][j]来
    # 当物品i的重量大于j，放不进来，保持原状 dp[i-1][j]
    # 否则，dp[i][j] = max(dp[i-1][j],dp[i - 1][j - weight[i]] + value[i])
    # dp[i - 1][j - weight[i]] + value[i]) j - weight[i]，预留出物品i的重量，放进i，并则增加i的value
    # 3.dp数组的初始化
    # dp[i][0]=0,dp[0][j] i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。 j < weight[0]的时候，dp[0][j] 应该是 0;当j >= weight[0]时，dp[0][j] 应该是value[0]
    # 4.确定遍历顺序
    # 从转移公式看，是从前向后遍历的，可以先遍历物品再遍历重量
    # 5.举例推导dp数组

0x5 今日收获，记录一下自己的学习时长

  • 1h

01背包问题 一维

https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-2.html

  • 遍历顺序不好理解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 1.定义dp数组，明确dp[j]的含义：
# 容量为j的背包，所背的物品价值可以最大为dp[j]
# 2.确定转移公式，
# dp[j]有两个选择，一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]，即不放物品i，一个是取dp[j - weight[i]] + value[i]，即放物品i，指定是取最大的
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
# 3.dp数组的初始化
# dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了
# 这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了
# 4.确定遍历顺序
# 物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！
# 倒序遍历是为了保证物品i只被放入一次！从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
    dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}
# 5.举例推导dp数组

0x5 今日收获，记录一下自己的学习时长

  • 1h

416. 分割等和子集

题目链接：https://leetcode.cn/problems/partition-equal-subset-sum/

0x1 看到题目的第一想法

0x2 自己实现过程中遇到哪些困难

  • 一维遍历顺序

0x3 今日学习的文章链接，或者视频链接

0x4 看完代码随想录之后的想法

  • dp[j]表示 背包总容量（所能装的总重量）是j，放进物品后，背的最大重量为dp[j]
  • dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
  • 如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历
    1
    2
    3
    4
    // 开始 01背包
    for i in range(len(nums)):
                for j in range(target, nums[i] - 1, -1):
                    dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])

0x5 今日收获，记录一下自己的学习时长

  • 1h

总结

  • 01背包的一维和二维实现

复习

  • day13
    • 二叉树的前中后序遍历

待重点复习

416