纯纯背包问题--(蒟蒻认为比较全)

发布时间 2023-11-28 16:21:42作者: 工作日摆烂

01背包,一般来说,这类背包唯一难点就是有时候你可能看不出来他的变形

比如下面一道题P1049 [NOIP2001 普及组] 装箱问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)这道题一般都可以看出来是01背包稍稍变形,把体积当作价值

下面这道P1164 小A点菜 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)是方案问题,要掌握最基本的一点就是

 这个是方案问题的状态转移方程

像这样的P1466 [USACO2.2] 集合 Subset Sums - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)就是方案背包然后稍加一点数学思考就可以ac掉的题

还有一种“能否到达”,是1即可以加,是0即不可,然后根据01还是无限去继续划分就好了

下面一种P1510 精卫填海 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)求满足要求的最小体力,一种最直接的方法就是先走背包,如果最大值大于要求,那么说明可以满足,然后遍历一遍找满足的最小体力;第二种方法就是反着来,把数组初始化为很大的数,然后把石子的体积看作体积,需要的体力看作价值,这个时候是求最小的背包

还有这样一种,做题时候需要稍微开动一下脑筋P2392 kkksc03考前临时抱佛脚 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)就是把背包折半来考虑