作者sorryChen (陈扬和)
看板Programming
标题算法问题
时间Fri Jun 1 11:13:00 2012
给定N个set, 规定至少选其中M个set, 使选的sets的集合包含的element个数越少越好
举例说明,一个往返两地的包车要服务N个客户中的至少M位,
每位客户有要搭车的日期表, 比如乘客一, 1,3,5, 乘客二, 1,2,3, 乘客三 1,15,30...等
包车希望在服务M位乘客的情况下发车日越少越好...需要写个程式来选乘客...
这难道会是一个NP Complete的问题吗?
和Set Cover或类似注明的NP-Complete应该不同吧
有没有高手能解惑
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 207.151.93.115
※ 编辑: sorryChen 来自: 207.151.93.115 (06/01 11:13)
1F：→ Lordaeron:是union 後的元素最少吧? 210.59.250.101 06/01 11:56
2F：→ Lordaeron:先sort每个SET的element,再删重覆(ALL) 210.59.250.101 06/01 11:58
3F：→ Lordaeron:再sort SET by element number 210.59.250.101 06/01 11:59
4F：→ Lordaeron:其中前M 个就是你要的. 210.59.250.101 06/01 11:59
5F：→ Lordaeron:N sets 有n element,sort 用nlgn 210.59.250.101 06/01 12:00
6F：→ Lordaeron:删重覆, 用n^2,有N sets, 再sort 210.59.250.101 06/01 12:01
7F：→ Lordaeron:用NlgN, 加一加, 不用polynomial time 210.59.250.101 06/01 12:02
8F：→ Lordaeron:对有进行过删重覆的才需要被第二次sort 210.59.250.101 06/01 14:38
9F：→ sorryChen:存一份copy没问题但还是不懂您怎麽选择 108.94.138.88 06/01 15:42
10F：→ Lordaeron:或者,loop n elements 去count出各 210.59.250.101 06/01 15:55
11F：→ Lordaeron:element 的个数. 再loop N sets, 去为它 210.59.250.101 06/01 15:56
12F：→ Lordaeron:所包含的elements 的count 作相加. 取 210.59.250.101 06/01 15:57
13F：→ Lordaeron:最大者. 210.59.250.101 06/01 15:57
14F：推 yoco315:可以问一下N跟m可能有多大吗?我猜很大啦XD182.235.170.158 06/03 19:35
15F：推 yoco315:好难 :( 本来想把 set cover problem 转成182.235.170.158 06/10 13:32
16F：→ yoco315:这个问题,但是失败了,没办法在P转换 >"<182.235.170.158 06/10 13:32
17F：→ neverfly:这个问题不是被证明是NPC了吗？ 114.32.224.229 06/10 22:39
18F：→ neverfly:喔，没看清楚题目，搞错了 114.32.224.229 06/10 22:40
19F：推 yauhh:这个问题很类似在图中找一段长度的路径,使 61.231.64.224 06/12 20:42
20F：→ yauhh:路径权重最小. 61.231.64.224 06/12 20:43
21F：推 Arton0306:似乎不像P的问题 114.42.50.185 06/12 20:46
22F：推 yoco315:不行... 还是想不到... orz 111.185.67.169 06/13 23:26