关于01分数规划问题
  • 板块灌水区
  • 楼主qzwh
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/3/23 13:22
  • 上次更新2023/10/28 05:53:14
查看原帖
关于01分数规划问题
438100
qzwh楼主2022/3/23 13:22

不加限制的01分数规划问题为什么不能直接用贪心每次获得当前性价比最高的物品呢,然后把总价值除以总代价不就是最优解吗,看的一般性解法都是先二分比率再贪心。 比如这一题\

【例题】 POJ2728最优比率生成树
_ 给定一张 N 个点、M 条边的无向图 (1 ≤ N,M ≤ 10000),图中每条边 e 都有一 个收益 Ce 和一个成本 Re。求该图的一棵生成树 T,使树中各边的收益之和除以成本 之和,即 CeeT Ce / ZeeT Re 最大。
\

能不能维护一个根据性价比从大到小排序的优先队列然后使用prime求最大生成树呢

2022/3/23 13:22
加载中...