网站程序合同,最近中文字幕在线mv免费,免费网站建设免代码,东北亚科技园里有做网站的吗背包问题
01背包理论基础
对于01背包问题#xff0c;物品下标为0到i#xff0c;对应的重量为weight[0]到weight[i]#xff0c;价值为value[0]到value[i]#xff0c;每个物品只可以取或不取#xff0c;背包最大容量为j的场景。
常见的状态转移方程如下#xff1a; dp[i…背包问题
01背包理论基础
对于01背包问题物品下标为0到i对应的重量为weight[0]到weight[i]价值为value[0]到value[i]每个物品只可以取或不取背包最大容量为j的场景。
常见的状态转移方程如下 dp[i][j]max(dp[i-1][j],dp[i-1][j-weight[i]]value[i])
其中dp[i][j]的含义是对于下标0到i的物品任意取放满足背包剩余最大容量为j的情况下能获得的最大价值。
那么dp[i][j]可以划分为两种情况
取了下标为i的物品其获得的最大价值为dp[i-1][j-weight[i]]value[i]没有取下标为i的物品其获得的最大价值为dp[i-1][j]
对于该数组的初始化需要初始化i或j分别为0的边界情况
i0 的情况如果 j weight[0]则我们可以取物品0此时dp[0][j] value[0]。否则我们无法放入物品0此时dp[0][j] 0。j0的情况都为0因为背包容量为0时无法装入任何物品。
而对于i和j都非零时的情况我们可以初始化成一个随意的值因为根据状态转移方程来看它的数组与它本身没有关系所以在dp数组赋值时都会被覆盖掉。
接着我们思考它的遍历顺序。 对于这种dp数组为二维数组的情况两层for循环是可以颠倒位置的。因为无论是先遍历背包还是先遍历物品都能保障遍历dp[i][j]时已经给dp[i-1][j]以及dp[i-1][j-weight[i]赋值了正确的数值了。 注意对于所有01背包问题都可以使用回溯算法来解决对于每个物品取或不取一共n个物品那么算法的复杂度就是2的n次方。所以一般回溯会超时。 状态压缩滚动数组
而关于刚刚的场景实际上我们还可以用一维数组来做也就是常说的状态压缩或者说滚动数组。
此时状态转移方程为dp[j]max(dp[j],dp[j-weight[i]]value[i])。 其中dp[j]的含义是任意取放物品满足背包 剩余最大容量为j 的情况下能获得的最大价值。
和二维的情况一样dp[j]可以划分为两种情况
取了下标为i的物品其获得的最大价值为dp[j-weight[i]]value[i]没有取下标为i的物品其获得的最大价值为dp[j]
首先我们思考一个问题为什么可以状态压缩 这是因为从二维数组的状态转移方程我们可以知道dp[i]的数据只依赖dp[i-1]层的数据譬如在计算dp[3]的时候我们就不再需要存储dp[1]的数据了。这种只依赖于有限的数据的情况我们都可以状态压缩。在这我们压缩成两行数据一行是dp[i-1]一行是dp[i]。
接着我们思考这个dp数组的初始化。
j为0代表对于下标0到i的物品任意取放背包最大容量为0时能获得的最大价值毫无疑问肯定都初始化为0。j非零此时因为状态转移方程中我们给dp[j]赋值时会比较其自身。所以应该初始化为一个负值。
然后就是遍历顺序。 虽然数组只有1层了但是因为状态转移方程里还是有i存在的所以遍历赋值还是有两层for循环的外层是遍历物品内层是遍历背包容量。而且必须先遍历物品再遍历背包容量且背包容量需要倒序遍历。
为什么背包容量需要倒序遍历呢 如果正序遍历dp[j - weight[i]]可能在同一轮更新后再次被使用导致相当于选择了同一个物品多次这就变成了完全背包问题。倒序遍历可以确保每个物品只被使用一次。
416. 分割等和子集
在这道题虽然没有明说物品的价值但实际上物品的价值就是等于它本身的重量。这样题目就转化为了遍历下标从0到i的物品任意拿取物品只能拿取1次满足重量为ans的情况 为此我们想到了01背包dp[j]表示遍历下标从0到i的物品任意拿取满足重量为j。当dp[j]ans也就是存在满足重量为ans的情况那么返回True
代码1最套板子的一集
class Solution:def canPartition(self, nums: List[int]) - bool:n len(nums)ans 0for i in range(n):ans nums[i]if ans%2:return Falseansint(ans/2)dp [0] * (ans1) for i in range(n):for j in range(ans, nums[i]-1, -1):dp[j] max(dp[j-nums[i]]nums[i], dp[j])if dp[ans]ans:return Trueelse:return False最原始的一版纯套板子。效率2370ms击败13.38%
代码2优化外层for循环
根据上面的代码我们可以看到其实我们不需要循环下标i我们只需要拿到数本身就好了所以直接用for num in nums
class Solution:def canPartition(self, nums: List[int]) - bool:n len(nums)ans 0for i in range(n):ans nums[i]if ans%2:return Falseansint(ans/2)dp [0] * (ans1) for num in nums:for j in range(ans, num-1, -1):dp[j] max(dp[j-num]num, dp[j])if dp[ans]ans:return Trueelse:return False效率2253ms击败18.18%。
代码3优化其他条件减少代码量
class Solution:def canPartition(self, nums: List[int]) - bool:n len(nums)ans sum(nums) # 优化点1用sum函数减少for循环if ans%2:return Falseansans//2 # 优化点2用//替代int转化dp [0] * (ans1) for num in nums:for j in range(ans, num-1, -1):dp[j] max(dp[j-num]num, dp[j])if dp[ans]ans:return Truereturn False效率2547ms击败8.48% 可以看到其实效率没有说提升但是代码量会少看起来更简洁。
代码4优化初始化条件效率最高
对于代码3我们还可以再优化。因为我们其实并不关心dp[ans]的值具体是多少也就是说我们并不在意最终能满足题意的方案数是多少我们只关心能不能满足那么初始化dp数组时就可以不用数值而是用布尔值。注意这里根据dp数组的含义那么dp[0]的初始化就一定是True
class Solution:def canPartition(self, nums: List[int]) - bool:n len(nums)ans sum(nums)if ans%2:return Falseansans//2dp [False] * (ans1) dp[0] Truefor num in nums:for j in range(ans, num-1, -1):if dp[j - num]:dp[j] Truereturn dp[ans]效率563ms击败75.46%
1049.最后一块石头的重量Ⅱ
这道题转化一下思路就可以变成和416. 分割等和子集一样的问题。 因为我们知道如果两堆石头的重量越相近那么相撞后可以留下的重量就越小。 也是求 任取其中的石块看背包能装下的这堆石块的最大重量 是否能越靠近目标数整体重量的一半。
class Solution:def lastStoneWeightII(self, stones: List[int]) - int:n len(stones)all_sum sum(stones)ans all_sum//2dp [0] * (ans1)for stone in stones:for j in range(ans, stone-1, -1):dp[j] max(dp[j], dp[j-stone]stone)return abs((all_sum - dp[ans])-dp[ans])效率19ms击败74.61%
494.目标和
这道题最难想的可能是不知道它和动态规划有什么关系。第一时间想的估计都是回溯去遍历每个元素取或不取。
但实际上这道题可以将所有元素分为两类一类是前面加的一类是前面加-的。那么就和1049.最后一块石头的重量Ⅱ非常类似。我们设正数集合的总和为pos负数集合的总和为neg那么存在以下逻辑
posneg sum
pos-neg target为此推出pos (targetsum)//2
也就是说相当于我们要遍历所有物品任意取放找到满足背包容量为(targetsum)/2的情况数是多少。
所以dp[j]的含义为遍历前i个物品任意取放满足背包容量为j的情况数。
那么首先关于边界条件的判断就有两种
pos不是整数。因为数组都是整数所以pos也一定是整数。pos小于0根据pos的定义应该是正数集合的总和那么不可能小于0。
代码如下
n len(nums)
all_sum sum(nums)if (targetall_sum)%2: # pos不是整数return 0pos (targetall_sum)//2if pos 0:# pos小于0return 0其次关于状态转移方程dp[j]dp[0]dp[1]dp[2]...dp[j-1]也就是 或者说dp[j]dpj]dp[j-nums[i]]或者说dp[j]dp[j-num] 为什么是累加 因为每个物品都可以选择取或不取所以对于每个j它的值是由所有可能的前一个状态转移而来的。具体来说dp[j]的值是由dp[j-1]、dp[j-2]、…、dp[0]这些状态转移而来的因为这些状态都可能在加入当前物品后达到j。
最后关于初始化在这我们要求的dp是情况数那么dp[0]应该是多少呢 实际上dp[0]应该是1。举个例子 nums [0]target 0 那么pos应该为1因为给0前面加上一个是一种情况。 最后的代码如下
class Solution:def findTargetSumWays(self, nums: List[int], target: int) - int:n len(nums)all_sum sum(nums)if (targetall_sum)%2:return 0pos (targetall_sum)//2if pos 0:return 0dp [0] * (pos1)dp[0] 1for num in nums:for j in range(pos, num-1, -1):dp[j] dp[j-num]return dp[pos]
效率18ms击败87.50%
总结
对于416. 分割等和子集题目实际上为给定一个重量为target的背包是否能装满这个背包转移方程为
dp[0] True
for num in nums:for j in range(target, num-1, -1):if dp[j - num]:dp[j] True对于1049.最后一块石头的重量Ⅱ题目实际上为给定一个重量为target的背包该背包能装的最大价值价值就是重量是多少 转移方程为
dp [0] * (target1)
for stone in stones:for j in range(target, stone-1, -1):dp[j] max(dp[j], dp[j-stone]stone)对于494.目标和题目实际上为给定一个重量为target的背包求装满这个背包的方案数是多少 转移方程为
dp [0] * (target1)
dp[0] 1
for num in nums:for j in range(target, num-1, -1):dp[j] dp[j-num]
