演算法›Ch3 動態規劃
第 29 題/共 40 題
◀ AL 29/40
29. Dynamic Programming、House Robber、遞迴關係式
#AL-03-029中Dynamic ProgrammingHouse Robber遞迴關係式

[10%] You are a process engineer managing a critical Lithography Machine. The machine has a strict Thermal Constraint:

Constraint: You cannot schedule production for two consecutive shifts. If Shift ii is active, Shift i−1i-1 and Shift i+1i+1 must be idle (cooling).

Data: The estimated Production Yield Value for the upcoming 13 shifts is listed below.

Shift IDS1S2S3S4S5S6S7S8S9S10S11S12S13
Value45954535854540856565403590

Questions:

(1) [4%] Identify the set of shifts that results in the maximum possible total value while satisfying the thermal constraint. (Selected Shifts、Total Value)

(2) [4%] A very important client demands that Shift 7 (Value: 40) MUST be included in the schedule. Under this mandatory condition, what is the maximum total value you can achieve for the 13 shifts? (Selected Shifts with S7、Total Value with S7)

(3) [2%] Process Upgrade: The High-Temperature Machine. Imagine the factory installs a new, high-performance machine. This machine generates significantly more heat, so the safety constraint is updated:

New Constraint: After any active shift, the machine must cool down for TWO consecutive shifts.

Let f[i]f[i] be the maximum value achievable considering shifts up to ii, and let viv_i be the value of Shift ii. Please write down the complete Recurrence Relation (Mathematical Equation) for f[i]f[i].

📄 成大115
跳轉到第題
▤完整推導請見《WH 資工筆記 · 演算法》Ch3 動態規劃
本章題號 · 21–40 / 40