AI & Data Dreamers練功房
寶箱片場規則
ALGO GATES・演算法關卡・高階・3 題

演算法高階・動態規劃

背包、最長上升子序列的條數、編輯距離:把指數級的列舉換成填表。

這一頁是題幹試閱;登入/註冊後每題可以在瀏覽器裡執行、對答案,第一次交對 +10 XP。

  1. 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 執行,只用標準函式庫。

    作答登入後可作答
  2. 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 執行,只用標準函式庫。

    作答登入後可作答
  3. 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 執行,只用標準函式庫。

    作答登入後可作答