代码随想录算法训练营第四十二天| 01背包理论基础、LeetCode416.分割等和子集

本文主要是介绍代码随想录算法训练营第四十二天| 01背包理论基础、LeetCode416.分割等和子集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

01背包理论基础

【二维数组】

1.确定dp数组以及下标的含义
- dp[i][j]的定义为：[0-i]之间的物品任取，放进容量为j的背包里
2.确定递推公式
- 分两种情况：
  - 放物品i:
    - dp[i-1][j-wight[i]]+value[i]
      - 当背包容量为j-weight[i]的时候不放物品i的最大价值
  - 不放物品i:
    - dp[i-1][j]
      - 当背包容量为j的时候不放物品i的最大价值
- 综合两种情况考虑：
  - dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])
3.确定dp数组如何初始化
- 1.将dp[i][0]全部初始化为0
  - 意思是当背包容量为0的时候，背包什么也放不了，因此总价值是0
- 2.将dp[0][j]全部初始化为物品0的价值
  - 意思是当背包只放物品0的时候，总价值就只为物品0的价值
  - 注意：当物品0的重量大于背包容量的时候，应该将背包价值初始化为0（因为放不下）
- 3.非零下标的初始化：
  - 初始化成什么都可以，因为非零下标全是根据前面的数值推导出来的，所以初始化成什么都不影响结果
4.确定遍历顺序
- 两层for循环：
  - 第一层遍历物品：
    - 第二层遍历背包容量：
      - 递推公式
- 注意：对于二维数组实现的背包问题，其实先遍历物品还是先遍历背包容量都可以
  - 因为我们当前数据总是由左上方和正上方的值推导出来的，只要确保左上方和正上方有值，遍历顺序就无所谓
5.举例推导dp数组
- 手动推导一下答案，然后将数组打印出来，看看每个状态是否是按照我们的思路进行转移的

【一维数组】

01背包理论基础（滚动数组）
- 1.确定dp数组以及下标的含义
  - dp[j]的定义为：容量为j的背包最大价值为dp[j]
- 2.确定递推公式
  - 分两种情况：
    - 放物品i:
      - dp[j-weight[i]]+value[i]
        
        当背包容量为j-weight[i]的时候不放物品i的最大价值
    - 不放物品i:
      - dp[j]
        
        当背包容量为j的时候不放物品i的最大价值
  - 综合两种情况考虑：
    - dp[j] = max(dp[j],dp[j-weight[i]]+value[i])
- 3.确定dp数组如何初始化
  - dp[0]=0
    - 意思是背包容量为0的时候，背包价值为0
  - 非零下标应该初始化为非负数里的最小值，因为我们需要不断地进行比较，取最大值更新
- 4.确定遍历顺序
  - 两层for循环：
    - 第一层遍历物品：
      - 第二层遍历背包容量：
        
        递推公式
  - 注意：因为一维数组每一层的数据是需要重复利用的，因此遍历顺序只能是倒序遍历
    - 我们需要倒序来保证每个物品添加一次，因为需要保证每个物品只添加一次，所以必须先遍历物品，再遍历背包
- 5.举例推导dp数组
  - 手动推导一下答案，然后将数组打印出来，看看每个状态是否是按照我们的思路进行转移的

LeetCode 416 分割等和子集

题目链接：416. 分割等和子集 - 力扣（LeetCode）

【解题思路】

可以把本题抽象成一个背包问题，每个数值就是价值和重量，我们装满[target]背包的价值=target就代表找到了
1.确定dp数组以及下标的含义
- dp[j]的定义为：容量为j的背包最大价值为dp[j]
2.确定递推公式
- dp[j] = max(dp[j],dp[j-nums[i]]+nums[i])
  - 因为重量和价值都是nums[i]
3.确定dp数组如何初始化
- dp[0]=0
  - 意思是背包容量为0的时候，背包价值为0
- 非零下标应该初始化为非负数里的最小值，因为我们需要不断地进行比较，取最大值更新
4.确定遍历顺序
- 两层for循环：
  - 第一层遍历物品：
    - 第二层遍历背包容量：
      - 递推公式
- 注意：因为一维数组每一层的数据是需要重复利用的，因此遍历顺序只能是倒序遍历
  - 我们需要倒序来保证每个物品添加一次，因为需要保证每个物品只添加一次，所以必须先遍历物品，再遍历背包
5.举例推导dp数组
- 手动推导一下答案，然后将数组打印出来，看看每个状态是否是按照我们的思路进行转移的

【解题步骤】

1.如果数组为空，或者数组长度为0，则return false
2.新建一个sum变量，统计nums数组的总和
3.如果总和为奇数，则不能平分，return false
4.定义一个target，初始化为总数的一半
5.定义一个dp数组，长度为target+1
6.先遍历物品，i<nums.length时停止遍历
- 再遍历背包，j>=nums[i]时停止遍历
  - 运用递推公式更新dp[j]
- 如果dp[target]=target，说明已经找到，无需再遍历，return true
8.return dp[target] == target