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 )