BackPack 1

Solution

[2, 3, 5, 6] S = 11

背包怎么装，使背包总共的容量最多。体积最大。

dp[i][j] = dp[i-1][j] or dp[i-1][j-A[i]];~~~~

可以填到11

Code

/**

 * @param m: An integer m denotes the size of a backpack
 * @param A: Given n items with size A[i]
 * @return: The maximum size
 */
int backPack(int m, vector<int> A) {
    // write your code here
    int n = A.size();
    if(n == 0)
    {
        return 0;
    }

    // initialize

    vector<vector<bool>> ret;
    for(int i = 0; i <= n; i++)
    {
        vector<bool> tmp(m+1, false);
        tmp[0] = true;
        ret.push_back(tmp);
    }

    // fill the dp matrix

    for(int i = 1; i < n+1; i++)
    {
        for(int j = 0; j < m+1; j++)
        {
            ret[i][j] = ret[i-1][j];
            if(j >= A[i-1])
            {
                ret[i][j] = ret[i][j] || ret[i-1][j-A[i-1]];
            }
        }
    }

    // return the answer

    for(int j = m; j >= 0; j--)
    {
        if(ret[n][j])
        {
            return j;
        }
    }

    return 0;
}