BackPack 3

Solution

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

每个物品可以被取多次，背包怎么装，使背包总共的价值最多.(最大价值)

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

1） 要不等于不选这个i时的价值。

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

3） 物品无限和物品单个的区别在于dp[i] or dp[i-1]

Code

/**

 * @param A an integer array
 * @param V an integer array
 * @param m an integer
 * @return an array
 */
int backPackIII(vector<int>& A, vector<int>& V, int m) {
    // Write your code here
    int n = A.size();
    if(n == 0)
    {
        return 0;
    }

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

    for(int i = 1; i < n+1; i++)
    {
        for(int j = 0; 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][j-A[i-1]] + V[i-1]);
            }
        }
    }

    return dp[n][m];
}