做分享衣服网站的初衷是什么,如何登陆wordpress,辽宁发布紧急通知,上海房地产网站建设01背包问题#xff1a;组合问题
题目 思路 将nums数组分成left和right两组#xff0c;分别表示相加和相减的两部分#xff0c;则#xff1a; left - right targetleft right sum 进而得到left为确定数如下#xff0c;且left必须为整数#xff0c;小数表示组合不存在组合问题
题目 思路 将nums数组分成left和right两组分别表示相加和相减的两部分则 left - right targetleft right sum 进而得到left为确定数如下且left必须为整数小数表示组合不存在 left (target sum)/2 所以问题转化为寻找 l e f t ( t a r g e t s u m ) / 2 left(target sum)/2 left(targetsum)/2的所有组合。 设 l e f t left left为背包最大容量则 d p [ l e f t ] dp[left] dp[left]表示装满背包的组合(路径)数 有哪些来源可以推出dp[j]呢 只要搞到nums[i]凑成dp[j]就有dp[j - nums[i]] 种方法。 例如dp[j]j为5 已经有一个1nums[i] 的话有 dp[4]种方法 凑成 容量为5的背包。 已经有一个2nums[i] 的话有dp[3]种方法 凑成 容量为5的背包。 已经有一个3nums[i] 的话有 dp[2]中方法 凑成 容量为5的背包 已经有一个4nums[i] 的话有 dp[1]中方法 凑成 容量为5的背包 已经有一个5 nums[i]的话有 dp[0]中方法凑成容量为5的背包 那么凑整dp[5]有多少方法呢也就是把 所有的 dp[j - nums[i]] 累加起来。 dp[j] dp[j - nums[i]] 而01背包求组合数的方法总结为 初 始 化dp[0] 1 其他为零 递推函数dp[j] dp[j - nums[i]] (物品重量 ≤ j ≤ 背包容量) for 循 环遍历背包容量依旧倒序 代码
二维数组易于理解
class Solution:def findTargetSumWays(self, nums: List[int], target: int) - int:total_sum sum(nums) # 计算nums的总和if abs(target) total_sum:return 0 # 此时没有方案if (target total_sum) % 2 1:return 0 # 此时没有方案target_sum (target total_sum) // 2 # 目标和# 创建二维动态规划数组行表示选取的元素数量列表示累加和dp [[0] * (target_sum 1) for _ in range(len(nums) 1)]# 初始化状态dp[0][0] 1# 动态规划过程for i in range(1, len(nums) 1):for j in range(target_sum 1):dp[i][j] dp[i - 1][j] # 不选取当前元素if j nums[i - 1]:dp[i][j] dp[i - 1][j - nums[i - 1]] # 选取当前元素return dp[len(nums)][target_sum] # 返回达到目标和的方案数一维数组简洁
class Solution:def findTargetSumWays(self, nums: List[int], target: int) - int:total_sum sum(nums) # 计算nums的总和if abs(target) total_sum:return 0 # 此时没有方案if (target total_sum) % 2 1:return 0 # 此时没有方案left (target total_sum) // 2 # 目标和dp [0] * (left 1) # 创建动态规划数组初始化为0dp[0] 1 # 当目标和为0时只有一种方案即什么都不选for i in range(len(nums)):for j in range(left, nums[i] - 1, -1): # 依旧倒序dp[j] dp[j - nums[i]] # 状态转移方程累加不同选择方式的数量return dp[left] # 返回达到目标和的方案数回溯法超时
class Solution:def backtracking(self, candidates, target, total, startIndex, path, result):if total target:result.append(path[:]) # 将当前路径的副本添加到结果中# 如果 sum candidates[i] target则停止遍历for i in range(startIndex, len(candidates)):if total candidates[i] target:breaktotal candidates[i]path.append(candidates[i])self.backtracking(candidates, target, total, i 1, path, result)total - candidates[i]path.pop()def findTargetSumWays(self, nums: List[int], target: int) - int:total sum(nums)if target total:return 0 # 此时没有方案if (target total) % 2 ! 0:return 0 # 此时没有方案两个整数相加时要注意数值溢出的问题bagSize (target total) // 2 # 转化为组合总和问题bagSize就是目标和# 以下是回溯法代码result []nums.sort() # 需要对nums进行排序self.backtracking(nums, bagSize, 0, 0, [], result)return len(result)
