Danamic Programing : 背包問題
==

>在M件物品裡取出若干件放在負重為W的背包裡，每件物品的重量為W1，W2，W3····Wn，與這些物品對應的價值分別對應為P1，P2，P3·· ···Pn，如何求出這個背包能裝的最大價值?
>

---

## 圖解法

解這類的提問，一般會先用圖解法，畫表格來解

方便起見，先將題目定為 ：

$M = 5, W = 16$
$W_1, W_2, W_3, W_4, W_5 = [3, 4, 7, 8, 9]$
$P_1, P_2, P_3, P_4, P_5 = [4, 5, 10, 11, 13]$

|$W/P$| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|----|----|----|----|----|----|----|
| 3 | 0 | 0 | 0 | 4 | 4 | 4 | 8 | 8 | 8 | 12 | 12 | 12 | 16 | 16 | 16 | 20 | 20 |
| 4 | 0 | 0 | 0 | 4 | 5 | 5 | 8 | 9 | 10 | 12 | 13 | 14 | 16 | 17 | 18 | 20 | 21 |
| 7 | 0 |0 |0 |4 |5| 5| 8| 10| 10| 12| 14| 15| 16| 18| 20| 20| 22 |
| 8 | 0 |0 |0 |4 |5| 5| 8| 10| 11| 12| 14| 15| 16| 18| 20| 21| 22 |
| 9 | 0| 0| 0| 4| 5| 5| 8| 10| 11| 13| 14| 15| 17| 18| 20| 21| 23 |

由表中可以得出：當揹包負重`W = 16`時，背包裡物品的最大價值`P = 23`

---

## 程式解法

以`Golang`為例 ：

func dp(objArr, valueArr []int, target int, compareFunc func(a, b int) int) int {
    // memorize data 初始化
    var res [][]int
    res = append(make([][]int, len(sourceArr)))
    for i := 0; i < len(sourceArr); i++ {
        res[i] = make([]int, target+1)
    }
    // 狀態轉換方程
    for i := 0; i < len(sourceArr); i++ {
        for j := 0; j <= target; j++ {        
            if i == 0 {
                res[i][j] = 0
            } else {
                if j == 0 {
                    res[i][j] = 0
                } else if objArr[i] > j {
                    res[i][j] = res[i-1][j]
                } else {
                    res[i][j] = 
                        compareFunc(valueArr[i]+res[i][j-objArr[i]], res[i-1][j])
                }
            }
        }
    }
    return res[len(sourceArr)-1][target]
}

這邊稍微解說一下
主要的邏輯是：

$F(m,n) = Min(P_m + F(m, n - W_m), F(m-1, n))$

意即是在背包負重為`n`公斤且第`m`個物體加進參考的當下，背包裡物體最大的總價值為$F(m,n)$
`compareFunc`在這個題目用的是類似`math.Max()`的方法，回傳輸入參數中較大的一方
實際輸入的參數是：
1. $P_m + F(m, n - W_m)$ => `m`物體的價值，加上當前負重`n`扣掉`m`的重量$W_m$後的最大價值
2. $F(m-1, n)$ => 前一列的解，即是`res[i-1][j]`

實際開始跑回圈時，會遇到一個小問題:
當輸入$m = 3$時，並沒有前一列的解可以參考，導致`res[i-1][j]`會發生·`index out of range`

為此，我用了一個小技巧來解決：__將$W$的最前面塞入一個0__，並且在迴圈中判斷，當$m = 0$時，res[i][j]一律為0

sourceArr := []int{0, 3, 4, 7, 8, 9}
...
if i == 0 {
    res[i][j] = 0
} esle if{
    ...
}
...

這就像是初始化的效果，會產出一列全都是0的陣列，供之後`compareFunc`參考
如此一來，當$m = 3$輸入時，`compareFunc`的另一個輸入值將會是前一列初始化的0
[看結果](https://play.golang.org/p/TdrWlWlqSpx)

###### tags: `Computer Science` `Algorithm` `Dynamic Programing`