BackPack 2

Solution

A = [2, 3, 5, 7] S = 11 V = [1, 5, 2, 4]

背包怎么装，使背包总共的价值最多.(最大价值)

dp[i][j] = dp[i-1][j] or dp[i-1][j-A[i]] + V[i];

1） 要不等于不选这个i时的价值。 2） 如果要选这个i的价值，看看 j - A[i] 是否大于0， 是的话再和dp[i-1][j-A[i]] + V[i]比较

Code

Code

/**

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

    int n = A.size();
    vector<vector<int>> dp;
    for(int i = 0; i<n+1; i++)
    {
        vector<int> tmp(m+1, 0);
        dp.push_back(tmp);
    }

    int ret = 0;

    for(int i = 1; i<n+1; i++)
    {
        for(int j = 1; j < m+1; j++)
        {

            dp[i][j] = dp[i-1][j];

            if(j >= A[i-1])
            {
                dp[i][j] = max(dp[i][j], dp[i-1][j-A[i-1]] + V[i-1]);
            }

            ret = max(ret, dp[i][j]);
        }
    }

    return ret;
}