etCode

这题不要被题目的示例给带偏其实就是看看我们能不能把石头尽量分成两堆比如示例的总和为

了。

即尽量分成重量总和近似相等的两堆就是想到本题的关键了这么看和416.

true

false本题是尽量凑凑不成就相撞所剩下的重量也是最小的。

dp

背包中背包容量为

dp[j]。

但本题的重量/容量也是它的价值所以这里的最大价值也是它的最大重量背包容量为

dp[j]递推公式在

背包中dp[j]Math.maxdp[j]dp[j-weight[i]]value[i]前者是不放物品

dp[j]Math.maxdp[j]dp[j-stones[i]]stones[i]前者是不放石头

idp

jtargetjstones[i]j–先物品后背包然后背包这一层从后往前遍历这里为什么jstones[i]

数组用于

target。

关于放“”还是“-”就是把这个集合分成了两个集合放加法的是一个集合放减法的是一个集合。

本题和416.

left减法用

集合有多少种方法就能找到符合题目条件的多少种组合这就是背包问题了left

true

II结束尽量去装能装多少装多少本题就是给我们一个容量问有多少种方式能把背包装满dp

装满背包容量为

种方法。

bagSizetargetsum/2递推公式dp[j]dp[j-nums[i]]

背包中

目标和就是给我们一个容量问有多少种方式能把背包装满本题是求装满这个背包最多有多少个物品dp

0、n

dp[j]Math.maxdp[j]dp[j-weight[i]]value[i]本题中我们物品的重量就是

就是物品的价值价值就是个数我们求的就是最多个数。

可以这么理解放了物品

i还剩下

被初始化值覆盖掉遍历顺序也是两层for循环先物品再背包。

先通过增强

for循环遍历

{//dp[i][j]表示i个0和j个1时的最大子集int[][]

new