# PDSA 期中考第七題

## 解答

function SOLUTION(items, M):
    ###### 建立 dp ######
    n = length(items) 
    dp = array of size (n+1) x (M+1) # 2D dp 

    for w from 0 to M:
        dp[0][w] = 0 
    
    for i from 1 to n:
        for w from 0 to M:
            if w_i > w:
                dp[i][w] = dp[i-1][w]
            else:
                dp[i][w] = max( dp[i-1][w], v_i + dp[i-1][w - w_i] )
    
    ###### 獲得 collection 中的 items ######
    w = M
    collection = [] 
    
    for i from n to 1:
        if dp[i][w] != dp[i-1][w]:
            add item i to collection
            w = w - w_i

    return dp[n][M], collection
    

## 講解
1. 建立一個 2D table, dp[*i*][*w*] 是指前面 *i* 個 items 和 剩餘容量 *w* 時所能達到的最大 value

n = length(items) 
dp = array of size (n + 1) × (M + 1)

2. 在沒有 item 時, 能獲得的 max value = 0

for w from 0 to M:
    dp[0][w] = 0 

3. 如果 w~i~ 大於剩餘容量 w 時, item~i~不會被放入，否則將會被拿取。跟加入前的 max value 比較後將新的 max value 存入 dp，一直算到 dp[n][M]。

for i from 1 to n:
    for w from 0 to M:
        if w_i > w:
            dp[i][w] = dp[i-1][w]
        else:
            dp[i][w] = max( dp[i-1][w], v_i + dp[i-1][w - w_i] )

4. 如果不等式成立, 代表 item~i~ 有被選中。將 item~i~ 加入 collection 中, 扣除 w~i~，一直算到 i = 1 得到完整 collection。

w = M
collection = [] 

for i from n to 1:
    if dp[i][w] != dp[i-1][w]:
        add item i to collection
        w = w - w_i

## 常見錯誤
1) dp table size 怎麼樣都不會是 w x v !! (批改時會對照 for loop 中使用的 indexing 邏輯)
3) dp table initialize: 在一開始, value 應該是0, 不會是1)
4) recursive 實作 for loop 更新邏輯錯誤, 但有寫出正確的 recursive relation 會部分給分
6) 變數命名請使用題目中有定義的變數、助教看得懂的命名方式或有另外附上說明 :)

## 配分
依照題義應該解出 "Which items to include in the collection ......", 但鑒於本題的作答情形過於慘烈, 本題給分放寬至只需要**實作完 dp table 即可獲得滿分**。

dp table: size (3 分) + initialize (2 分)
中間recursive 判斷 (8 分）(如果有寫出正確的recursive relation 但實作有錯誤部分給分 3 分)
變數名稱: 2 分 (有寫點東西, 名稱不要太奇怪)