背包dp题单
-
背包dp1: (分组背包)
-
题目大意: t组数据每组一个n一个m,代表n种病,m为预算,问分散资金最多能救治多少病人
-
解题思路: 分组背包看病的花费为v救活人数为w,因为病有阈值性正好对应了分组背包每组只能选一个的特点,分组背包的滚动数组优化不同于01背包,01背包直接对应的是物品,用i来循环物品选与不选最大值直接能够更新到上面去,但是分组背包i对应的是组数,每组里面的个体的选与不选要在其组中更新出到该位置的最大值
背包dp1: (分组背包)
题目大意: t组数据每组一个n一个m,代表n种病,m为预算,问分散资金最多能救治多少病人
解题思路: 分组背包看病的花费为v救活人数为w,因为病有阈值性正好对应了分组背包每组只能选一个的特点,分组背包的滚动数组优化不同于01背包,01背包直接对应的是物品,用i来循环物品选与不选最大值直接能够更新到上面去,但是分组背包i对应的是组数,每组里面的个体的选与不选要在其组中更新出到该位置的最大值
相关推荐