CII2187-一般任务安排问题的最小费用最大流解法及其他

Matrix posted @ 2008年7月22日 05:14 in Problem Analysis with tags 任务安排问题最小费用最大流 , 2308 阅读

by F.Yang

CII-2187问题描述：一人以看录像维生. 每个录像有三个属性 (s, f, p) 分别表示该任务的开始时间，结束时间和所得收入. 但这个人在同一时刻最多只能看两个录像. 现给定 n 个录像. 问这个人的最大收入是多少.

分析： 我们把问题一般化, 设这个人在同一时刻最多能看 k 个电影. 我们使用最小费用最大流来解决这个问题.

把每个任务的开始时间和结束时间都对应设为图的一个顶点. 对每个任务 (s, f, p), s 结点到 f 结点连一条弧, 容量为1, 费用为 -p. 而对任意两个任务(si, fi, pi), (sj, fj, pj), 如果fi<=sj, 则从 fi 到 sj 连一条弧, 容量为1, 费用为0. 设一超级源 R0, R0 到各个任务的开始时间 si 都连一条容量为1, 费用为0的弧. 再设一超超级源 R1, R1仅有到R0容量为k, 费用为0的弧. 最后设一超级汇 R2, 各任务的结束时间 fi 到R2都有一条容量为1, 费用为0的弧.

求从 R1 到 R2 的最小费用最大流, 得到费用 cost, 则 -cost 即为问题的答案.

讨论： 虽然上述算法在一般化的角度解决了这个问题, 但是由于解决费用流的算法复杂度约为 O(N^3) , 这在某些有特殊限制的问题变种里并不见得是一种首选的高效算法. 现在总结一下一些特殊的变种及适合的方法.

(1) 单资源无费用. 如果上题那个人任一时刻只能看一个录像, 并且每看一个录像的收入都是1, 那么这是一个经典的活动安排问题. 任务按结束时间排序后使用贪心算法即可解决. 算法的时间复杂度为 O(NlogN)+O(N)=O(NlogN) .

(2) 单资源有费用. 如果上题观看者每一时刻都只能看一个录像. 任务按结束时间排序后使用一个DP即可, 设 dp[i] 表示以任务 i 结束的情况下所能获得的最大收益. 该算法的时间复杂度为 O(NlogN)+O(N^2)=O(N^2) .

      (3) 多资源无费用. 如果上题里观看者每一时刻最多可以看k个录像, 但是看每个录像的收入都是1. 可以使用如下算法解决:
      a. 维护一个数据结构T, 表示各个资源的最后可用时间, 初始时里面有k个0;
      b. 将任务按结束时间排序;
      c. 顺序扫描每个任务 (s, f), 在 T 里面查找一个不大于 s 的最大的元素 t. 如果能找到, 则选取该任务, 并将 t 更新为 f 加入回 T 中, 若不能找到 t, 则放弃该任务.
      T使用平衡树来维护, 每次查找和更新的复杂度为 O(logK) , 整个算法的复杂度为 O(NlogN)+O(NlogK)=O(N(logN+logK)) . 但编码的复杂度很大.

(4) 两资源有费用. 这即为原题本身. 可以使用两维状态的三方dp来解决. 小伟已经使用该方法通过了该题. 呼唤小伟给出算法详解和代码.

[回复]

jackyseo15 说:
2022年2月03日 23:02 The author is energetic about acquiring wooden furniture on the web and his investigation about best wooden furniture has realized the plan of this article. Tera Mera Saath Rahe

[回复]

KVS Sample Paper 说:
2022年9月28日 16:36

KVS Sample Paper 2023 Pdf Download for Kendriya Vidyalaya Sangathan Class 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 & 12 Arts, KVS Sample Paper Science & Commerce Stream Practice Paper Suggestions with Past years old exam Solved Question Bank for all Regional Students of English Medium, Hindi Medium & Urdu Medium Studying in KVS Schools across the Country. All the Kendriya Vidyalaya Sangathan Board Students can download the Sample Paper Suggestions with Model Papers along with Previous Years old Exam Solved Question Bank for all Languages & Subjects of the Course.

[回复]

Covid 19 Vaccine Reg 说:
2022年10月27日 00:27

Covid 19 pandemic is spreading fast and becoming overwhelming for many countries globally. The Indian central government is finding ways to prevent and protect the citizens from the severe pandemic. Covid 19 Vaccine Registration 2023 Recently the government has announced the vaccination of citizens in the age gap of 18 + years. This quite a relief as the vaccination was first established for the old, vulnerable groups and frontline workers such as health practitioners.

[回复]

Anonymous 说:
2023年1月03日 14:59

I read this article. I think You put a great deal of exertion to make this article. I like your work. 강남가라오케

[回复]

Anonymous 说:
2023年1月03日 15:04

Your blogs further more each else volume is so entertaining further serviceable It appoints me befall retreat encore. I will instantly grab your rss feed to stay informed of any updates. 안전놀이터

[回复]

Anonymous 说:
2023年1月06日 12:23

Beaver says I also have such interest, you can read my profile here: 안전놀이터

[回复]

TJ Maxx Credit Card 说:
2023年1月27日 21:29

TJ Maxx also well known as TJMaxx or TJX, is a superstore chain in United State of America that is famous for selling products at lower prices compared to other superstore chains in the market. TJ Maxx Credit Card In order to increase their customers intent they have launched a special credit card called TJMaxx credit card. This may used in any of their stores. Upon using these cards customers will earn loyalty and bonus points. This loyalty and bonus points used in order to redeem through special offers.

[回复]

woodworking stores n 说:
2023年3月02日 21:03

woodworking near me growing day by day in the market and this industry also needs a current website to enhance its online business. It can help them to inaugurate the reliability of the brand in the market. Flexible web designs permit brands to adjust the look and content to their existing goals. Lots of woodworking shops near me are working on the online market.

[回复]

Nagaland 5th Class 说:
2023年7月11日 19:23

Nagaland Board 5th Textbook 2024 Provide in School Wise Free Distbrution in Government School, SCERT Nagaland Primary School Various Class Complete Students Do not Waste Summers Holidays, Download SCERT Nagaland 5th Class Textbook 2024 Nagaland Regular Practice new Lessions for Students Best idea Students Method.SCERT Nagaland Textbook 2024 Download Available Official Website, Our Portal Provide SCERT Nagaland Primary School Books 2024 Download, Hindi Medium, English Medium and Urdu Medium Textbooks

[回复]

mi actividad 说:
2023年7月27日 00:01 Todos pueden usar la página Mi actividad de Google para eliminar una gran parte o la totalidad de su historial de búsqueda. Eliminar o borrar su historial y actividad de búsqueda de Google solo eliminará los elementos ingresados en los productos de Google, mi actividad como la línea de tiempo de Google Maps, el historial de ubicación , las fotos , YouTube Watch y la actividad de búsqueda , etc.

[回复]

pavzi.com 说:
2024年1月09日 01:55 Pavzi website is a multiple Niche or category website which will ensure to provide information and resources on each and every topic. Some of the evergreen topics you will see on our website are Career, Job Recruitment, Educational, Technology, Reviews and others. pavzi.com We are targeting mostly so it is true that Tech, Finance, and Product Reviews. The only reason we have started this website is to make this site the need for your daily search use.

CII2187-一般任务安排问题的最小费用最大流解法及其他

Matrix

分类

最新评论

最新留言

友情链接

功能

浏览计数器