演算法高階・動態規劃
背包、最長上升子序列的條數、編輯距離:把指數級的列舉換成填表。
這一頁是題幹試閱;登入/註冊後每題可以在瀏覽器裡執行、對答案,第一次交對 +10 XP。
- 01
夜間批次視窗挑任務-knapsack_01
困難動態規劃夜間批次視窗只有 W 分鐘。待排的任務各有執行時間(分鐘)與價值分數,每個任務最多跑一次、不能拆開。請挑一組任務,總執行時間不超過 W,讓價值總和最大;價值總和一樣大的選法中,取總執行時間最短的。
輸入:
第 1 行:任務數 n 與視窗長度 W
接下來 n 行:
任務名 執行分鐘 價值(正整數)輸出:兩行
第 1 行:最大的價值總和
第 2 行:達到這個價值總和所需的最短總執行時間
要求:用 0/1 背包的動態規劃(O(n×W)),不要列舉子集合(36 個任務有 2^36 種組合)。
範例輸入:
5 100
etl_orders 40 30
etl_users 30 20
rebuild_idx 60 45
backup 50 25
vacuum 10 5
範例輸出:
75
100
類型對應:LeetCode「0/1 Knapsack」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答 - 02
收盤價最長上升段的條數
困難動態規劃分析師想知道一段期間的收盤價裡,「嚴格上升的子序列」(不必連續,但要照時間順序)最長有多長,以及長度達到最長的子序列有幾條。兩條子序列只要挑的日子不同就算不同條(價格相同也算)。
輸入:
第 1 行:組數 t
接下來 t 行:每行一組收盤價(整數,以空白分隔,至少一筆),或
GEN n seed lo hi。GEN開頭的行是大量測資的縮寫:starter 已寫好gen(),讀進來後跟一般的 list 一樣,不用自己處理。輸出:每組一行
最長長度 條數(條數可能很大,照實印出,不取餘數)。要求:用動態規劃同時記「以第 i 天結尾的最長長度」與「達到這個長度的條數」,O(n²) 即可;不要列舉子序列。
範例輸入:
2
3 1 4 2 5
7 7 6
範例輸出:
3 3
1 3
類型對應:LeetCode「Number of Longest Increasing Subsequence」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答 - 03
跨系統欄位名稱比對
困難動態規劃兩套系統的欄位命名習慣不同(
cust_id對customer_id、ord_amt對order_amount)。資料整合時先用編輯距離自動配對:把一個字串變成另一個字串,每次可以插入一個字元、刪除一個字元或換掉一個字元,最少要幾步就是編輯距離。對每個來源欄位,找出編輯距離最小的目標欄位;距離一樣小時取名稱字典序最小的(Python 字串比較)。最小距離超過門檻就視為配不到。同一個目標欄位可以被多個來源欄位配到。
輸入:
第 1 行:門檻 d
第 2 行:來源欄位名稱(以空白分隔)
第 3 行:目標欄位名稱(以空白分隔)
輸出:每個來源欄位一行,照輸入順序:
來源 -> 目標 距離;最小距離大於 d 時印來源 -> NONE。要求:編輯距離用動態規劃表(O(len(a)×len(b)))計算,不要用遞迴列舉所有編輯方式。
範例輸入:
3
usr_id amt zz
user_id amount ts
範例輸出:
usr_id -> user_id 1
amt -> amount 3
zz -> ts 2
類型對應:LeetCode「Edit Distance」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答

送件鴿飛出去了