第二课《背包瘦身术——01背包优化》1、 上节课回顾上节课我们认识了背包王国最有名的魔法 01背包2、每件物品要么选1 要么不选03、状态定义dp[i][j]表示前 i 件物品背包容量为 j能获得的最大价值。4、转移方程dp[i][j] max( dp[i-1][j], dp[i-1][j-w[i]] v[i] )同学们已经学会了如何解决01背包问题。5、可是今天阿宝遇到了新的麻烦……第一幕仓库爆炸了阿宝成为了王国最厉害的宝物收集师。1、一天国王送来一个超级任务物品数量1000件 背包容量10000阿宝开心地写出int dp[1001][10001];2、结果……电脑直接崩溃了3、为什么会崩1我们来算算。数组大小1000 × 10000 1000万一个 int4字节需要1000万 × 4 4000万字节 ≈ 40MB2如果题目再大一点5000 × 10000直接上百MB比赛根本放不下。第二幕汉克老师提供新方法1、汉克老师说阿宝你有没有发现其实你根本不需要保存整张表2、阿宝啊为什么3、汉克老师拿出了状态转移dp[i][j] max( dp[i-1][j], dp[i-1][j-w[i]]v[i] )4、然后问你看看dp[i][j] 只依赖谁5、阿宝观察dp[i-1][...]咦只依赖上一行第三幕发现秘密1、假设现在计算dp[5][7]需要dp[4][7]和dp[4][7-w]2、计算完第5行以后第3行还重要吗不重要第2行还重要吗不重要第1行呢也不重要3、汉克老师笑着说所以你根本不需要保存所有历史。只需要保存当前结果第四幕背包瘦身术诞生1、原来dp[i][j]可以压缩成dp[j]2、含义变成dp[j]表示容量为 j 时目前能获得的最大价值。3、二维数组dp[1001][10001]压缩为 ↓一维数组dp[10001]4、空间从1000万格变成10000格直接瘦身1000倍第五幕神奇转移1、还记得原来的公式dp[i][j] max( dp[i-1][j], dp[i-1][j-w[i]]v[i] )2、压缩以后dp[j] max( dp[j], dp[j-w[i]]v[i] )3、看起来很简单阿宝兴奋地写for(int i1;in;i) { for(int jw[i];jm;j) { dp[j]max( dp[j], dp[j-w[i]]v[i] ); } }4、结果……答案错了第六幕可怕的重复阿宝很疑惑。于是汉克老师带他来到算法实验室。1、一个宝物只有重量价值110背包容量42、正确答案应该是多少当然是10因为只能拿一次3、阿宝使用正序循环for(j1;j4;j)开始计算。1j1dp[1] max(0,dp[0]10) 10得到0 10 0 0 02j2此时dp[1] 10于是dp[2] dp[1]10 20变成0 10 20 0 03j3dp[3] dp[2]10 304j4dp[4] dp[3]10 40最终0 10 20 30 404、阿宝惊呆了我明明只有一个宝物怎么拿了4次第七幕找到问题关键1、问题关键就是正序循环2、因为当计算dp[2]时使用的dp[1]已经是本轮更新后的结果。于是同一个宝物被反复利用。3、效果变成拿一次 拿两次 拿三次 拿四次4、这已经不是01背包了变成了我们后面要学的完全背包第八幕倒序循环1、汉克老师说想保证每件物品只用一次必须倒着更新2、写成for(int jm;jw[i];j--)3、为什么因为当计算dp[j]时dp[j-w[i]]还没有被本轮修改。仍然是上一轮的结果。4、这样就保证一个物品最多使用一次第九幕理解倒序1、还是这个宝物重量价值110容量4初始0 0 0 0 02、倒序1j4需要dp[3]还是0得到0 0 0 0 102j3需要dp[2]还是0得到0 0 0 10 103j2需要dp[1]还是0得到0 0 10 10 104j1得到0 10 10 10 103、结果正确无论容量多大都只能拿一次第十幕01背包优化模板这是竞赛中最常用的模板。#include iostream #include algorithm using namespace std; int main() { int n,m; cinnm; int w[1005]; int v[1005]; for(int i1;in;i) { cinw[i]v[i]; } int dp[10005]{0}; for(int i1;in;i) { for(int jm;jw[i];j--) { dp[j]max( dp[j], dp[j-w[i]]v[i] ); } } coutdp[m]; return 0; }第十一幕如何判断要不要倒序这是竞赛中的超级口诀1、每件物品只能选一次例如宝物 课程 题目 商品只能选一次。那么必须倒序for(jm;jw;j--)2、为什么保证当前物品不会重复使用第十二幕举一反三看到下面题目立刻想到01背包优化。例1考试得分时间120分钟每道题耗时 分数每题只能做一次。求最高得分。容量时间价值分数 01背包例2购物节预算500元商品价格 快乐值每件只能买一次。求最大快乐值。 01背包例3课程选择时间20小时课程耗时 收益每门只能选一次。 01背包 本课重要结论结论1二维dp[i][j]可以压缩成dp[j]结论201背包转移dp[j] max( dp[j], dp[j-w[i]]v[i] )结论301背包必须for(jm;jw[i];j--)倒序一句话口诀01背包倒着跑 每件宝物拿一遭。 正序更新会出事 同个宝物重复捞 课后挑战背包容量5物品物品重量价值宝剑26盾牌210药水312请同学们第一关用二维DP求答案。第二关改成一维DP。第三关故意把代码改成for(jw[i];jm;j)正序循环。观察结果。思考为什么答案变大了哪个宝物被偷偷重复使用了如果你能彻底搞懂这个问题那么你已经真正掌握了01背包优化的灵魂