作者Lordaeron (Terry)
站内Programming
标题Re: 算法问题 (从N个set选m个包含最少的元素)
时间Mon Jun 4 07:38:40 2012
※ 引述《sorryChen (陈扬和)》之铭言：
: ※ 引述《sorryChen (陈扬和)》之铭言：
: : 给定N个set, 规定至少个set, 使选的sets的集合包含的element个数越少越好
: 请原谅不太懂推文中所写的所以举例一下
: ex: S0={0}, S1={1}, S2={2},S3={3}, S4={1,2}, S5={1,2}, S6={2,3}, S7={1,3}
: 假设都排好了
: M=4好了, 选S1,S2,S4,S5
: M=7好了, 选S1,S2,S3,S4,S5,S6,S7, 反正不选S0, 想说排序选前面的不见得最好
:
※ 发信站: 批踢踢实业坊(ptt.cc)
: ◆ From: 207.151.93.115
: ※ 编辑: sorryChen 来自: 207.151.93.115 (06/01 12:24)
: → Lordaeron:删重覆後, s1~s7都为空, 有问题吗? 210.59.250.101 06/01 12:59
: → sorryChen:不懂怎麽删重复耶 删调有帮助吗? 108.94.138.88 06/01 15:39
: → sorryChen:若有重复过的element都删去吗,那若都删 108.94.138.88 06/01 15:40
: → sorryChen:如何选择 108.94.138.88 06/01 15:40
: → sorryChen:那要怎麽选择呢 ? 108.94.138.88 06/01 15:41
init :S0={0}, S1={1}, S2={2},S3={3}, S4={1,2}, S5={1,2}, S6={2,3}, S7={1,3}
1.S0={0}, S1={}, S2={2},S3={3}, S4={,2}, S5={,2}, S6={2,3}, S7={,3}
2.S0={0}, S1={}, S2={},S3={3}, S4={,}, S5={,}, S6={,3}, S7={,3}
3.S0={0}, S1={}, S2={},S3={}, S4={,}, S5={,}, S6={,}, S7={,}
so, S4={,}, S5={,}, S6={,}, S7={,} 为所选,因为被删的element count 最大的
由
→ stimim:选 4567 有 {1,2,3} 选 1245 只有 {1,2} 140.112.49.204 06/04 08:27
所讲,
所以加上已知1,2 被删4 次, 3. 被删3 次.
这会不会比较好选? 有这麽多已知条件, 还需要指数时间来找吗?
我不会证了. 请高人吧.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 1.162.12.97
1F：→ stimim:选 4567 有 {1,2,3} 选 1245 只有 {1,2} 140.112.49.204 06/04 08:27
2F：→ Lordaeron:噢, 哪就选少的罗 210.59.250.101 06/04 10:25
3F：→ yauhh:增增删删就化简成联集差集,就简单了.218.160.110.179 06/04 10:29
4F：→ Lordaeron:你要用数学的方式表达,高兴就好 210.59.250.101 06/04 10:38
5F：→ yauhh:不是表达不表达,而是你这种算法黑手动作修来218.160.110.179 06/04 11:44
6F：→ yauhh:修去,不觉得很累吗?其实就只是求差集而已.218.160.110.179 06/04 11:45
7F：→ Lordaeron:哦..没辨法, 算法黑手就是这样罗. 210.59.250.101 06/04 12:07
8F：→ Lordaeron:你写程式可以直接求集的就好罗 210.59.250.101 06/04 12:09
9F：→ yauhh:我认为是把不同层次的东西混在一起,才变黑手218.160.110.179 06/04 12:09
10F：→ Lordaeron:求差集的 210.59.250.101 06/04 12:09
11F：→ yauhh:但没有人都是用直接求的啦,做资料结构不难.218.160.110.179 06/04 12:10
12F：→ Lordaeron:不难啊,等你罗. 210.59.250.101 06/04 12:14
13F：→ Lordaeron:反正我是演算法黑手,跟你不同. 210.59.250.101 06/04 12:14
14F：→ Lordaeron:你还是快推导一下,我的方法会不会有错吧 210.59.250.101 06/04 12:15
15F：推 yauhh:楼上,我已经回文指出你的方法有错. 59.112.227.2 06/10 06:48
16F：→ yauhh:我觉得当你不确定你自己很对,不要太自信满满 59.112.227.2 06/10 06:50
17F：→ Lordaeron:楼下的, 自信满满的是你吧, 怎麽算到我 1.162.1.146 06/10 06:55
18F：→ Lordaeron:身上来了. 1.162.1.146 06/10 06:55
19F：→ Lordaeron:别人回过1245了,还要你特别发一篇? 1.162.1.146 06/10 06:58
※ 编辑: Lordaeron 来自: 1.162.1.146 (06/10 07:04)
※ 编辑: Lordaeron 来自: 1.162.1.146 (06/10 07:08)
20F：→ yauhh:原po指明我回文中第一方法有错,我已经承认. 59.112.227.2 06/10 07:12
21F：→ yauhh:这样说来,我是怎麽自信满满了? 59.112.227.2 06/10 07:12
22F：→ yauhh:至於我文中第二方法,是老实将所有(N,M)组合 59.112.227.2 06/10 07:13
23F：→ yauhh:拿出来找最少合并数,这是暴力法,当然有信心. 59.112.227.2 06/10 07:14