01分数规划学习笔记

290 字
1 分钟
01分数规划学习笔记

起因:P1642 规划

说实话我的印象里是做过这种题的,但是当时好像理解后就跑路了,现在来复习一下。

什么是01分数规划呢?

其实就是让你跑一个01背包,但是物品有三个权值,重量都为1,然后让你求选的物品的剩下两个权值比值最大,也就是性价比。

这种东西在没有选择依赖关系的情况下看起来确实可以贪心,但是这样就没意思了,所以我们来说说有依赖关系怎么求,对于最普通的01分数规划问题来说一般都是二分答案,也就是我们要求的那个最优的性价比。

之后我们根据这个平均性价比,反推出一个物品相对于平均值的贡献,然后就可以大力用各种各样的dp求出当前的最大值了,如果大于0就说明还有优化空间,反之则没有。

要退役了,什么最优比率生成树,什么最优比率环也不打算学,就这样吧。

文章分享

如果这篇文章对你有帮助,欢迎分享给更多人!

01分数规划学习笔记
https://rechenz.github.io/post/01分数规划学习笔记/
作者
热尘
发布于
2023-11-16
许可协议
CC BY-NC-SA 4.0

评论区

Profile Image of the Author
热尘
游戏开发者 · AI 爱好者
公告
欢迎来到我的博客!这是一则示例公告。
分类
标签
站点统计
文章
38
分类
5
标签
12
总字数
46,029
运行时长
0 天
最后活动
0 天前
站点信息
构建平台
GitHub Actions
博客版本
Firefly v6.16.8
文章许可
CC BY-NC-SA 4.0

当前页面没有目录

文章目录

当前页面没有目录