---
# System prepended metadata

title: 'ADA 8.1: Fractional Knapsack Problem'
tags: ['ADA 8.1: Fractional Knapsack Problem']

---

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

# ADA 8.1: Fractional Knapsack Problem


回顧 Huffman Codes

# Multiple Choices

![](https://i.imgur.com/VczsLq1.png)


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


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

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

![](https://i.imgur.com/M9BXPZV.png)

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

![](https://i.imgur.com/ev61pcJ.png)

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

![](https://i.imgur.com/htz4B42.png)

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

![](https://i.imgur.com/pxVWWW3.png)

T' 一定會是T的global OPT

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



# Knapsack Problem 背包問題

![](https://i.imgur.com/hnMhVwt.png)


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



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

![](https://i.imgur.com/5WQwtKW.png)

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


![](https://i.imgur.com/tforWbi.png)

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





![](https://i.imgur.com/oH8CwmA.png)


考量到兩種情況

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

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


![](https://i.imgur.com/91LUiMV.png)


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

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


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

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

![](https://i.imgur.com/VyiiCFw.png)

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

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


