01分数规划学习笔记
290 字
1 分钟
01分数规划学习笔记
起因:P1642 规划
说实话我的印象里是做过这种题的,但是当时好像理解后就跑路了,现在来复习一下。
什么是01分数规划呢?
其实就是让你跑一个01背包,但是物品有三个权值,重量都为1,然后让你求选的物品的剩下两个权值比值最大,也就是性价比。
这种东西在没有选择依赖关系的情况下看起来确实可以贪心,但是这样就没意思了,所以我们来说说有依赖关系怎么求,对于最普通的01分数规划问题来说一般都是二分答案,也就是我们要求的那个最优的性价比。
之后我们根据这个平均性价比,反推出一个物品相对于平均值的贡献,然后就可以大力用各种各样的dp求出当前的最大值了,如果大于0就说明还有优化空间,反之则没有。
要退役了,什么最优比率生成树,什么最优比率环也不打算学,就这样吧。
文章分享
如果这篇文章对你有帮助,欢迎分享给更多人!
相关文章智能推荐
1
01BFS学习笔记
算法竞赛2023-10-25
2
关于dp状态转移方程的设计4
算法竞赛2026-07-18
3
cs224n学习笔记
人工智能2026-01-18
4
关于动态规划的转移1
算法竞赛2023-11-01
5
基础神经网络学习笔记
人工智能2025-11-02
随机文章随机推荐

