[問題] Costed Sorting 的演算法
請教一下costed sort的作法... 一個頭兩個大...
基本要求是這樣，給一串數字，用兩兩交換的方式來sort，但是每個sort要
花代價...
例如 sort {3, 2, 1}
先把 1,2 對調變成 {3, 1, 2} -> 代價為 1+2 =3
然後把 1,3 對調 {1, 3, 2} -> 代價為 1+3 =4
最後換 2,3 {1, 2, 3} -> 代價為 2+3 =5 => 總代價為 12
題目要求要找出最小代價的算法，以這題來說當然是 1 跟 3 直接對調，總代價 = 4
我一開始的想法是先sort找出最後的正確數列，然後從最小代價的數字組開始互換
，直到數列正確。例如
8124 -> 8214(3 cost) -> 8241(cost 5) -> 1248(cost 9)
但是遇到數字跳很大的就出問題了，例如18976
我的作法會是
18976 -> 16978 (14) -> 16798 (16) -> 16789 (17) = 47
但正確的最小代價解法是
18976 -> 68971 (7) -> 68179 (10) -> 68719 (8) -> 61789 (9) -> 16789 (7) = 41
這樣的問題到底該怎麼解呢？
--
英文翻譯： Are you longsome tonight?
版本 A： 今晚，你是龍神嗎？
版本 B： 你是龍神吐奶嗎？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 75.143.81.79
→
11/13 12:44, , 1F
11/13 12:44, 1F
→
11/13 12:45, , 2F
11/13 12:45, 2F
→
11/13 12:52, , 3F
11/13 12:52, 3F
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 1 之 7 篇)：