ㄜ....我之前那篇好像明显的超越课程进度的样子.... (这并不跟我的程设强度正相关....) 可是,既然是我提出这些名词的, 我想,我应该还是要尽我那浅薄的知识解释一下 (其实我比较希望有那位高人来救我....) 1.Greedy中译贪婪法 简单说就是像老师讲的酿,先填大的,在依次填入较小的 典型问题:找硬币 例如,今天要凑出87元好了,目标是让硬币数最小 那用新台币的硬币来看,我们就先用一个50元,接着是10元三个 一个5元、两个1元, 这就是最佳解(反正很少看到莫那鲁道,就忽略一下) holymars所提供的补充是,在每个硬币的币值都是比他大的硬币币值的因数时, Greedy确保有最佳解,原因是,小的塞不满,大的也一定填不满 方法一的修正,可说便是由此而来,因为5是25的因数,一定能填满货柜 之後2是8的因数,所以应该就能用Greedy找到最佳解 遗憾的是,後来我找到反例...(原本以为终於可以简单写完这题...) 2.BFS=Breadth(?) First Search,广度优先搜寻 其实这是对图形进行"拜访"的一种方法(假设我没记错...) ....我需要图...可是我不会用bbs画图... 总之,就这题来讲,现在如果8还有剩,就把放一个8的状况,存起来 ,然後塞到某个暂存的地方(这有名字的,可是我不想再惹麻烦了...) 对5、2做一样的事情,然後从刚刚塞东西的地方,把最先放进去的那个拿出来 重复这样的动作,并且对每个填完的状况比较,输出货柜数最小的解 简而言之,把每种放置顺序都找出来,其实这就是暴力法啦... 所以我说...应该确定能找到最佳解...可能也最花时间 3.DP=Dynamic Programming,动态规划 一言以蔽之,建表!!!,(其实我最不敢说我会的就是这种演算法) 用这题作范例,先考虑货柜大小只有1的状况,把此时的状况记在表中 再看大小为2,3,4.....的情形,然後视题目要求,找出最佳解, 也许这题不是酱DP...有可能我弄错意思, 基本上 这些都是资料结构与演算法的东西,没记错的话,这是大二的课... 所以,绝对不要在意自己不知道这些东西, 这一切都是因为教授自己以为Greedy一定有最佳解, (就像香蕉讲的,要是她xxx有给数字,我们或许可以判断 到底是不是只要Greedy就行了) 结果不行(只要有反例就算不行) --------------------------------这是乱入--------------------------- 在物理上 推翻一条定理很简单,找到反例就行了, 让假说变定理要很久,有证明,不够,要经过长时间的验证 ---《爱因斯坦怎麽想》似乎是从这出来的... --------------------------------乱入结束--------------------------- 所以,这题突然变成难度极高的问题(就我以大一计程的程度来看) 我也觉得突然爆Greedy那些的出来很诡异... 真希望...题目改成某个人在用Greedy装货,要我们预测结果就好了.... 绝对花的时间不会太长 -- 人类是绝对无法真正彼此了解的,但人类却总是试着了解他人 人类就是这麽悲哀的生物 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.239.64