[理工] [計概] NP-complete BST LCS

看板Grad-ProbAsk作者 (Firefighter)時間14年前 (2012/02/14 07:51), 編輯推噓1(1推 0噓 4→)
留言5則, 2人參與, 最新討論串1/1
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
推
02/14 17:34, , 1F
2.取log看大概2的幾次方
02/14 17:34, 1F
→
02/14 17:37, , 2F
3.LCS位置不用一樣，algm沒錯
02/14 17:37, 2F
→
02/14 17:39, , 3F
小偷背包分0-1和fractional解法 前者為DP 後者Greedy
02/14 17:39, 3F
→
02/14 17:40, , 4F
有看懂意思應該就會寫了 traveling-saleman有請高手
02/14 17:40, 4F
→
02/14 23:04, , 5F
取log看大概2的幾次方 我看不出來..太大了= =
02/14 23:04, 5F
‣ 更多 dunkjames 的文章
文章代碼(AID): #1FEQ7t9d (Grad-ProbAsk)