背包dp题单

  • 背包dp1: (分组背包)

  • 题目链接: 2020-03-14 2021年度训练联盟热身训练赛第二场 E: NIH Budget

  • 题目大意: t组数据每组一个n一个m,代表n种病,m为预算,问分散资金最多能救治多少病人

  • 解题思路: 分组背包看病的花费为v救活人数为w,因为病有阈值性正好对应了分组背包每组只能选一个的特点,分组背包的滚动数组优化不同于01背包,01背包直接对应的是物品,用i来循环物品选与不选最大值直接能够更新到上面去,但是分组背包i对应的是组数,每组里面的个体的选与不选要在其组中更新出到该位置的最大值

  • code: https://paste.ubuntu.com/p/qqkckGqd4Z/

全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

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