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 )
全部评论

相关推荐

05-26 09:07
已编辑
门头沟学院 Java
点赞 评论 收藏
分享
小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务