# Backpack

###### tags: `Medium`

## Question
* 在 n 个物品中挑選若干物品装入背包，最多能装多滿？假設背包的大小為 m，每个物品的大小為 A[i]

先確認i個物品是否以放入m大小的空間，再逐一增加物品數量放入m大小的空間看看，形成一個二維矩陣，其中每個元素紀錄物品數量對應空間大小能否滿足(true/false)，每次確認都和前一次有關，該次大小要滿足外，前一次的紀錄也要是true

int backPack(int m, vector<int> &A) {
    // f[i][j] 前i个物品，是否能装j
    // f[i][j] =f[i-1][j] f[i-1][j-a[i] j>a[i]
    // f[0][0]=true f[...][0]=true
    // f[n][X]
    int n = A.size();
    vector<vector<int>> f(n + 1, vector<int>(m + 1));
    
    f[0][0] = true;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= m; j++){
            f[i][j] = f[i - 1][j];
            if(j - A[i - 1] >= 0 && f[i - 1][j - A[i - 1]]){
                f[i][j] = true;
            }
        }
    }
    
    for(int i = m; i >= 0; i--){
        if(f[n][i]) return i;
    }
    
    return 0;
}