Day35| 动规和背包变形
今天三道题目，可以说分别是背包问题的不同变形
三个模型
- 已知每个物品的重量和价值。背包空间大小为Space，求放入物品的最大的价值。变形一 在和的上限不超过 half 的情况下的最大和。
- 已知每个物品的重量和价值。背包空间大小为Space，求装满背包的方法数量
- 已知每个物品的重量和价值。背包空间大小为Space，求背包最大可以放的数量。
最后一块石头的重量
这题实际上求得是 在和的上限不超过 half 的情况下的最大和。
基础背包模型求得是 空间和上限不超过 half 的情况下的最大价值和。
观察可以发现，如果将重量和价值相等的话，我们可以得到一个化简的式子也就是题目所有的内容。转换成代码就是这样
目标和
这题实际上就得是一个序列里面和为 sum 的个数。显然遍历回溯是可以解的。同时这有个最优子结构。
dp [i] [space] = dp[i-1] [space] + dp[i-1][space-space[i]]
对每个物品进行遍历即可。 对这个问题进行抽象我们可以得到 这样的背包问题。
- 已知每个物品的重量和价值。背包空间大小为Space，求装满背包的方法
474.一和零
这题实际上问的是
- 已知每个物品的重量和价值。背包空间大小为Space，求背包最大可以放的数量。
- dp [i] [space] = max( dp[i-1] [space] , dp[i-1][space-space[i]] +1 )
