###### tags: `ADA 8.1: Fractional Knapsack Problem`

# ADA 8.1: Fractional Knapsack Problem

回顧 Huffman Codes

# Multiple Choices


兩個項目merge在一個，兩個例子變成一個root，兩個node合成一個node
所需要encode的node數量變少，，某種程度上變成sub problem

原本的問題optimal solution(黃色)跟sub problem的(橘色)之間的關係
像是選擇哪一個choice，兩個選項合在一起，剩下的是sub problem

要證明的是不管merge哪個，都會得到後面（黃色的）OPT


實際上考慮的，X.Y merge成Z
左右的差異在於 freq(z) = freq(X) + freq(Y)


藉由找到的OPT s'回推原本的OPT s，如果OPT s'是最小OPT s也會是最小
須要證明的是Merge X,Y 會到groble 的OPT


兩個之間的關係，ＸＹ變成Ｚ


T' 一定會是T的global OPT

<!-- 任何兩個都可以符合到OPT -->

# Knapsack Problem 背包問題


n個背包，n個價值，物品不能拿超過的價額

這堂課探討最後一個，物品可以只拿部分（例如蛋糕可以切多塊）


單位價值最高的item要優先拿（每單位最高單價的應該先拿)，然後一直拿，值到超過背包重量為止


subproblem
前i個item要拿滿w的重量，目標找到F-KP(n,w)


考量到兩種情況

1. item i 有被拿，不論整個或部分
會是F-KP(i-1, w-w')

1. itme i不在裡面，不需要考量itemi
會是F-KP(i-1,w)


選擇greedy choice: 選擇最高單位價的物品vi/wi

透過反正法證明做的greedy choice可以證明

1. 當Ｗ<wj，表示wj可以取代包所有的東西，可以將J替換掉W
1. 當W>Wj，因為第J個item會是目前單位值最高的value，替換掉會提升overall 的value（不明白為何ＱＱ

以上兩種都會保證total value會比較好


可以思考如果沒有可以拿部分的情況，其他類型的背包問題，有沒有現在這個的property？

不是，為什麼？
是，可以一個通用的可以解其他問題？