0-1背包问题理论基础 分割等和子集

• 1. 0-1背包问题理论基础(二维数组实现)
• 2. 0-1背包问题理论基础 二（一维数组实现）

1. 0-1背包问题理论基础(二维数组实现)

背包问题一般分为这几种：

0-1背包问题：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

二维dp数组01背包

• 确定dp数组以及下标的含义
  对于背包问题，有一种写法， 是使用二维数组，即dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
• 确定递推公式
  再回顾一下dp[i][j]的含义：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
  那么可以有两个方向推出来dp[i][j]，
  • 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以被背包内的价值依然和前面相同。)
  • 放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值
    所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
• dp数组如何初始化
• 确定遍历顺序 先遍历物品更好理解。
• 举例推导dp数组

def test_2_wei_bag_problem1(bag_size, weight, value) -> int: rows, cols = len(weight), bag_size + 1dp = [[0 for _ in range(cols)] for _ in range(rows)]# 初始化dp数组. for i in range(rows): dp[i][0] = 0first_item_weight, first_item_value = weight[0], value[0]for j in range(1, cols): 	if first_item_weight <= j: dp[0][j] = first_item_value# 更新dp数组: 先遍历物品, 再遍历背包. for i in range(1, len(weight)): cur_weight, cur_val = weight[i], value[i]for j in range(1, cols): if cur_weight > j: # 说明背包装不下当前物品. dp[i][j] = dp[i - 1][j] # 所以不装当前物品. else: # 定义dp数组: dp[i][j] 前i个物品里，放进容量为j的背包，价值总和最大是多少。dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cur_weight]+ cur_val)print(dp)if __name__ == "__main__": bag_size = 4weight = [1, 3, 4]value = [15, 20, 30]test_2_wei_bag_problem1(bag_size, weight, value)

2. 0-1背包问题理论基础 二（一维数组实现）

def test_1_wei_bag_problem():weight = [1, 3, 4]value = [15, 20, 30]bag_weight = 4# 初始化: 全为0dp = [0] * (bag_weight + 1)# 先遍历物品, 再遍历背包容量for i in range(len(weight)):for j in range(bag_weight, weight[i] - 1, -1):# 递归公式dp[j] = max(dp[j], dp[j - weight[i]] + value[i])print(dp)test_1_wei_bag_problem()

416. 分割等和子集

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

只有确定了如下四点，才能把01背包问题套到本题上来。

• 背包的体积为sum / 2
• 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
• 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
• 背包中每一个元素是不可重复放入。
  以上分析完，我们就可以套用01背包，来解决这个问题了。

class Solution:def canPartition(self, nums: List[int]) -> bool:target = sum(nums)if target % 2 == 1: return Falsetarget //= 2dp = [0] * 10001for 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])return target == dp[target]