分數背包（fractional knapsack）

你是個帶著固定承重布袋的小偷，站在一堆堆貴重物品前——金粉、銀屑、寶石。每種物品有總價值與總重量，而關鍵是你可以取任意「分數」的一堆，而非只能整份取。取哪些物品、各取多少，能讓你帶走的價值最大？這就是分數（可分割）背包。

貪婪規則是把物品依價值密度排序——價值除以重量，即一公斤的價值——並從最密者往下裝。取盡最密的物品，再取盡次密的，依此類推，直到遇到無法整份放入者；只取「那個」物品剛好夠的量，把袋子精準填到容量上限。因為物品可分割，你絕不浪費容量，也絕不在更高價值的一公斤仍可取時還背著較低價值的一公斤。交換論證：若任何最佳裝法背著某較低密度物品的一公斤，而較高密度物品的一公斤被留下，就把那低密度的一公斤換成高密度的一公斤——同重、嚴格更高價值，與最佳性矛盾。故依密度的貪婪為最佳。依密度排序 O(n log n) 後，裝填為 O(n)。

分數背包是教科書中的正面例子，與它著名的失敗雙胞胎成對出現。它的 0/1 表親——你必須整件取或不取——不服從這條貪婪規則，因為一旦物品不可分割，你可能被迫留下一小段容量空著，而一個高密度物品可能太重放不進，但兩個較低密度物品合起來反而更好。可分割性是樞紐。在這裡可證為最佳的同一個密度貪婪，只差一個假設就可證為次佳。