作者dunkjames (Firefighter)
看板Grad-ProbAsk
標題[理工] [計概] NP-complete BST LCS
時間Tue Feb 14 07:51:16 2012
1.請問該如何用簡短敘述的方式(20~50字)提出 小偷背包 跟 旅行推銷者的可能解決辦法
2.假設有十E個數 大概是2^30 次方 如果使用二元搜尋法 最多只要比較31次
就能判斷出某數有沒有在其中[ log 2^30+1 ]取上限=31
如果有10兆 . 一千萬....各需要比較幾次?
3. president 跟 providence 的LCS用眼睛看就能知道是PRIDEN
可是algorithm 跟 alignment 用眼睛卻看不出來
為何答案是 algm
LCS=最長共同子序列
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 42.73.200.118
推 zensword:2.取log看大概2的幾次方 02/14 17:34
→ zensword:3.LCS位置不用一樣，algm沒錯 02/14 17:37
→ zensword:小偷背包分0-1和fractional解法 前者為DP 後者Greedy 02/14 17:39
→ zensword:有看懂意思應該就會寫了 traveling-saleman有請高手 02/14 17:40
→ dunkjames:取log看大概2的幾次方 我看不出來..太大了= = 02/14 23:04