← 回首頁

貪心(活動選擇 / 分數背包)

找錢時,店員總是先抓面額最大的硬幣,不夠再換小的——每一步都拿當下最划算的、拿了就不反悔。貪心(Greedy)就是這種「每步挑眼前最好、絕不回頭」的策略,好處是又快又直覺; 缺點是它不萬能,只有問題結構「剛好」讓局部最好能拼出全域最好時才保證正確。這頁挑兩個「貪心真的最優」的經典題:活動選擇(排進最多不衝突的時段)與 分數背包(有限容量下裝出最高總價值)。下面你會看到排序後如何一步步取捨,以及為什麼這樣選不會選錯。

貪心(Greedy)策略每步都選擇當下看起來最好的選項,並不回頭修正;只有在問題具備特定結構(如「貪心選擇性質」+「最優子結構」)時, 局部最佳才能被證明導出全域最佳。這裡示範兩個可證明安全的經典案例: 活動選擇(區間排程)——依結束時間排序後貪心選取,可用「交換論證」證明不劣於任何最優解; 分數背包——物品可分割時,依單位重量價值(CP 值)降序貪心取物即為最優解。 (對照組:0/1 背包物品不可分割,貪心通常不最優,需靠動態規劃求解,本頁不展開。)

1. 活動選擇(Activity Selection)

把所有活動依結束時間排序(同結束時間再依開始時間、原始索引排序);排序後第一個活動一定選; 之後依序考慮每個活動,開始時間 >= 目前最後選中活動的結束時間就選它並更新「最後結束時間」,否則跳過。

固定示範(同 activity-selection.test.js ACTIVITIES,CLRS 風格 8 活動):[1,4) [3,5) [0,6) [5,7) [3,9) [5,9) [6,10) [8,11)
已考慮活動數(considered):0
橫軸為活動起訖時間,縱軸為依結束時間排序後的序位;灰色=尚未輪到考慮;紅色(粗)=目前正在考慮的活動;綠色=已選入排程的活動。 線段旁數字為排序後的列序位(非原始活動索引,原始索引請對照右側面板)。

排序清單(依結束時間;序位 / 原始索引 / 開始 / 結束)

決策記錄(逐步累積)

已選活動(依原始索引)

2. 分數背包(Fractional Knapsack)

先計算每個物品的 CP 值(價值/重量),依 CP 值降序排序(同值則原始索引小者優先); 依序考慮每個物品,剩餘容量足夠就全部取走,否則取「剩餘容量/重量」的比例後容量歸零、結束。 取的比例以最簡分數字串顯示(整數運算約分),避免浮點小數顯示誤導。

固定示範(同 fractional-knapsack.test.js KNAPSACK,CLRS 經典範例):weights=[10,20,30]、values=[60,100,120]、capacity=50(教科書已知解 totalValue=240)
已取物品數(taken):0
表格依 CP 值降序排列(第一列為表頭),高亮列為目前正在考慮/取走的物品;「取的比例」欄即時更新。

總價值 / 剩餘容量

總價值 totalValue
0
剩餘容量 remaining
0

取的比例(依原始物品序)