作者yauhh (哟)
看板Programming
标题Re: 算法问题 (从N个set选m个包含最少的元素)
时间Sun Jun 10 06:35:44 2012
※ 引述《Lordaeron (Terry)》之铭言：
: 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 最大的
这种解释方法太恐怖. 你可能认为会,发生重覆而删掉的位置,代表那些集合合并之後
增加总共元素的数目的机会会减低,所以最後你要挑删掉的元素项目较多的集合,但是,
显然是忽略了其他没有重覆元素存在,然而并不会增加合并元素数目的集合.
例如:
S0={0}, S1={1], S2={2}, S3={3}, S4={1,2}, S5={1,2}, S6={2,3}, S7={3,4}
1.因为1有重覆所以删掉全部的1:
S0={0}, S1={], S2={2}, S3={3}, S4={,2}, S5={,2}, S6={2,3}, S7={3,4}
2.因为2有重覆所以删掉全部的2:
S0={0}, S1={], S2={}, S3={3}, S4={,}, S5={,}, S6={,3}, S7={3,4}
3.因为3有重覆所以删掉全部的3:
S0={0}, S1={], S2={}, S3={}, S4={,}, S5={,}, S6={,}, S7={,4}
4.已经没有重覆了所以依照被删掉的元素数目,由大到小排序:
S4={,}, S5={,}, S6={,}, S7={,4}, S1={], S2={}, S3={}, S0={0}
5.因为指定要的M sets, M数目为4,所以取前四个sets:
S4 U S5 U S6 U S7 = {1,2,3,4}
S4 U S5 U S6 U S7 是你所提删除方式的结果,虽然它是原po所言 "数目越少越好"
的潜在解之一, 但是这个情况,是 S1 U S2 U S4 U S5 = {1,2} 答案比较好.
而且你的方法所找出来的解,不但品质差,而且相当差.
实作上很难实作,答案是否适当也要看情况,而且也没有相当的道理让人相信
这演算法是对的.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 59.112.227.2
※ 编辑: yauhh 来自: 59.112.227.2 (06/10 06:53)
1F：→ Lordaeron:所以,你求出最佳解的做法是? 1.162.1.146 06/10 06:56
2F：→ Lordaeron:再说, 1245的问题, 已经有人回了 1.162.1.146 06/10 06:57
3F：→ Lordaeron:应该不用你发一篇文章来讲,因为你还是 1.162.1.146 06/10 06:57
4F：→ Lordaeron:後知後觉的哪位. 1.162.1.146 06/10 06:57
5F：→ yauhh:我求不错的解的做法,在我前文中第二方法中. 59.112.227.2 06/10 07:04
6F：→ yauhh:至於所谓後知後觉,其实是不知不觉,因为我根 59.112.227.2 06/10 07:05
7F：→ yauhh:本没想要破解你的方法,是从理解你的方法之後 59.112.227.2 06/10 07:05
8F：→ yauhh:看出漏馅之处. 59.112.227.2 06/10 07:05
9F：→ Lordaeron:别人已经讲过了. 你是没看别人的回文? 1.162.1.146 06/10 07:06
10F：→ Lordaeron:何苦去将他人的话转述一次当作自己的呢 1.162.1.146 06/10 07:07
11F：→ yauhh:那又怎麽样?最起码我发表了自己的破解解释. 59.112.227.2 06/10 07:07
12F：→ Lordaeron:对了,你还未证明你的做法是P, 不是NP 1.162.1.146 06/10 07:07
13F：→ Lordaeron:要当算法高手, 还要证明哦. 1.162.1.146 06/10 07:07
14F：→ yauhh:我不需要证明方法是NP,因为并没有讨论这一点 59.112.227.2 06/10 07:08
15F：→ yauhh:你说我说的是别人讲过的事情,对,因为在本文 59.112.227.2 06/10 07:15
16F：→ yauhh:张贴之前,我根本看不懂你的方法究竟怎麽做. 59.112.227.2 06/10 07:15
17F：→ yauhh:你描述的时候前後说词修来修去,黑手动作多, 59.112.227.2 06/10 07:16
18F：→ yauhh:是到前一位bob板友质疑才看明白你所讲的. 59.112.227.2 06/10 07:17
19F：→ Lordaeron:你看不懂没关系,有别人看出问题了 1.162.1.146 06/10 07:17
20F：→ yauhh:可见你讲了这个方法有多难懂. 59.112.227.2 06/10 07:18
21F：→ Lordaeron:你不知不觉而已,再说是不是NP才是发 1.162.1.146 06/10 07:18
22F：→ Lordaeron:问者的重点,你连别人问什麽都不知,回 1.162.1.146 06/10 07:18
23F：→ yauhh:讲方法讲的别人不懂,这也是演算学者的大忌. 59.112.227.2 06/10 07:18
24F：→ Lordaeron:得比我还要爽, 实在是佩服. 1.162.1.146 06/10 07:19
25F：→ yauhh:少来一套,你也没有解释你的方法是不是NP. 59.112.227.2 06/10 07:19
26F：→ yauhh:为什麽我突然要回答方法是不是NP? 59.112.227.2 06/10 07:20
27F：→ Lordaeron:哈....你真的是一个不看文的人.....不行 1.162.1.146 06/10 07:20
28F：→ Lordaeron:不看文而回文,是回文的大忌 1.162.1.146 06/10 07:20
29F：→ yauhh:你是说你推文中说你方法是P那样子吗?但是, 59.112.227.2 06/10 07:20
30F：→ Lordaeron:请回去看原po 的问题, 谢谢罗. 1.162.1.146 06/10 07:20
31F：→ yauhh:你的方法错,所以P或NP,没用,不是吗? 59.112.227.2 06/10 07:21
32F：→ yauhh:那你到底要不要承认你犯了错? 59.112.227.2 06/10 07:21
33F：→ Lordaeron:不要但是了, 不看问题而回文, 也是 1.162.1.146 06/10 07:21
你在讲什麽? 你说你的推文重要到值得看吗?
抱歉,我只看原po的问题. 至於你自己制造的问题,请自己收拾.
34F：→ yauhh:如果不要承认,那就不要罗唆罗,我还接到水球 59.112.227.2 06/10 07:21
35F：→ Lordaeron:演算学者的大忌. 1.162.1.146 06/10 07:22
36F：→ yauhh:要我加油,我就不知道是要加什麽油 59.112.227.2 06/10 07:22
※ 编辑: yauhh 来自: 59.112.227.2 (06/10 07:23)
37F：→ Lordaeron:错什麽? 我从没说过我对过 1.162.1.146 06/10 07:22
38F：→ Lordaeron:你真的要加油, 连原po 在问什麽都不知 1.162.1.146 06/10 07:23
39F：→ Lordaeron:就回文了, 嗯演算学者的大忌. 1.162.1.146 06/10 07:23
40F：→ Lordaeron:但还好, 我不是演算学者. 1.162.1.146 06/10 07:23
41F：→ yauhh:你连推同一组推文二次,有什麽意义? 59.112.227.2 06/10 07:24
42F：→ yauhh:我也不是演算学者啊 59.112.227.2 06/10 07:24
43F：→ Lordaeron:原po 就在问这是不是NP 问题了,大哥 1.162.1.146 06/10 07:24
44F：→ yauhh:他是问这问题是不是NP,而不是解法是不是NP. 59.112.227.2 06/10 07:25
45F：→ Lordaeron:哇, 还有问题跟解法分离的说法? 1.162.1.146 06/10 07:25
46F：→ Lordaeron:记住, 我是黑手, 不是学者, 没大忌.没差 1.162.1.146 06/10 07:26
47F：→ yauhh:你第一篇回文只说像是P 59.112.227.2 06/10 07:26
48F：→ yauhh:说错了,你第一篇推文只说是P. 59.112.227.2 06/10 07:26
49F：→ yauhh:所以你就是说,方法被抓到错,不当一回事. 59.112.227.2 06/10 07:27
50F：→ Lordaeron:是啊, 我推导如推文所述 1.162.1.146 06/10 07:27
51F：→ yauhh:第二篇推文,你没有提到P or NP. 59.112.227.2 06/10 07:27
52F：→ yauhh:第三篇推文是我和原po的对话. 59.112.227.2 06/10 07:27
53F：→ Lordaeron:不当一回事,有人连 1.162.1.146 06/10 07:28
54F：→ Lordaeron:"问题是不是NP,而不是解法是不是NP"都跑 1.162.1.146 06/10 07:28
55F：→ yauhh:第五篇推文,你根本没有提P or NP. 59.112.227.2 06/10 07:28
56F：→ Lordaeron:出来了. 再说, 我是黑手, 不是学者 1.162.1.146 06/10 07:28
57F：→ yauhh:第六篇bob板友提问,你用回文方式处理,但是, 59.112.227.2 06/10 07:28
58F：→ yauhh:但是你那篇回文虽然回了,但是解答中看得出 59.112.227.2 06/10 07:29
59F：→ Lordaeron:不用但是了. 你的问题NP,解不NP, 我输了 1.162.1.146 06/10 07:29
60F：→ yauhh:漏馅漏很多. 自删了. 59.112.227.2 06/10 07:29
61F：→ Lordaeron:你继续吧, 我们读的书不同,没什麽好讲的 1.162.1.146 06/10 07:30
62F：→ yauhh:至於现在你一直在说我不看人家的文,但是我 59.112.227.2 06/10 07:30
63F：→ Lordaeron:加油. 1.162.1.146 06/10 07:30
64F：→ yauhh:核对发现我都有看啊. 你的确没有讨论P or NP 59.112.227.2 06/10 07:30
65F：→ yauhh:那你说说这个问题是不是NP? 59.112.227.2 06/10 07:31
66F：→ yauhh:咦,我都已经这样很有诚意跟你核对文章内容.. 59.112.227.2 06/10 07:33
67F：→ Lordaeron:问题NP or not, 解法NP or not, 想请问 1.162.1.146 06/10 07:33
68F：→ yauhh:你到底在哪里做了"是否为NP"的讨论? 59.112.227.2 06/10 07:33
69F：→ Lordaeron:出自何书之说, 让我拜读一下吧. 1.162.1.146 06/10 07:34
不好意思,不屑分享. 因为到此我感觉你很没有诚意.
70F：→ yauhh:我承认我并没有讨论NP. 那你说我该讨论NP, 59.112.227.2 06/10 07:34
71F：→ yauhh:为什麽你不讨论呢? 59.112.227.2 06/10 07:34
※ 编辑: yauhh 来自: 59.112.227.2 (06/10 07:35)
72F：→ Lordaeron:不屑分享. 因为到此我感觉你很没有诚意. 1.162.1.146 06/10 07:36
73F：→ Lordaeron:哈.............. 1.162.1.146 06/10 07:36
74F：→ yauhh:如果你不是心虚,不会这样缠着我的推文不放. 59.112.227.2 06/10 07:37
75F：→ yauhh:那我离开programming板罗,星期天要轻松,bye 59.112.227.2 06/10 07:38
76F：→ Lordaeron:见鬼呢,连po问什麽都没看就回文的人, 还 1.162.1.146 06/10 07:40
77F：→ Lordaeron:可以说别人心虚,实在是佩服. 1.162.1.146 06/10 07:41
78F：→ Lordaeron:这倒底是谁在闹呢, hohoho.. 1.162.1.146 06/10 07:42
79F：推 sorryChen:实在不好意思, 让两位兄台替我费心了 108.94.138.88 06/11 15:21
80F：→ Lordaeron:我的看法, 不是NP problem 210.59.250.101 06/11 16:21
81F：→ Lordaeron:你去理哪个问题NP解NP 的干嘛呢. 210.59.250.101 06/11 16:21
82F：→ yauhh:可是是你自己去强调是否NP的,这会儿突然变 59.112.231.99 07/01 19:43
83F：→ yauhh:别人去理NP不NP. 至於原po既然问了NP不NP, 59.112.231.99 07/01 19:44
84F：→ yauhh:你又要後来否定原po的问题,你很矛盾耶. 59.112.231.99 07/01 19:44