19. 一座工廠有四條生產線 A、B、C、D，每天固定啟動一條生產線，但同一 條生產線不能連續兩天運作。已知 ?????[?][?]表示第 i 天啟動第 j 條生產 線時可獲得的產值，其中 j 可為 A、B、C、D。若以 ??[?][?] 表示「第 ? 天啟動第 ? 條生產線時，從第 1 天到第 ? 天可得到的最高總產值」，下列 哪一個遞迴關係式(recurrence relation)最適合用來計算 ??[?][?]？
(A) ??[?][?] = ?????[?][?] + max ?≠? ??[? − 1][?]
(B) ??[?][?] = ?????[?][?] + max ?≠? ??[?][?]
(C) ??[?][?] = ?????[?][?] + max ?≠? ??[? − 2][?]
(D) ??[?][?] = max ?≠? (?????[?][?] + ??[? − 1][?])

答案：登入後查看
統計： A(2), B(0), C(2), D(2), E(0) #3911385

詳解 (共 2 筆)

#7408734
正確答案： A 解析： 第 i 天啟動...
(共 436 字，隱藏中）
前往觀看
1
0
#7490662

解析：

題目限制「同一條生產線不能連續兩天運作」，
因此第 i 天若選擇產線j，則前一天（第 i-1天）所選的產線 k 必須與 j 不同（k≠ j）。

  • 最佳子結構轉移式為：第 i 天選擇產線 j 的產值 value[i][j]，加上前一天選擇其他任意不同產線所累積的最大產值：

    dp[i][j] = value[i][j] + max dp[i-1][k]
0
0