LintCode 125. 背包问题 II（DP）

样例 1:
输入: m = 10, A = [2, 3, 5, 7], V = [1, 5, 2, 4]
输出: 9
解释: 装入 A[1] 和 A[3] 可以得到最大价值, V[1] + V[3] = 9 

样例 2:
输入: m = 10, A = [2, 3, 8], V = [2, 5, 8]
输出: 10
解释: 装入 A[0] 和 A[2] 可以得到最大价值, V[0] + V[2] = 10

class Solution {
public:
    int backPackII(int m, vector<int> &A, vector<int> &V) {
        int n = A.size(), i, j;
        vector<vector<int>> dp(n,vector<int>(m+1,-1));
        dp[0][0] = 0, dp[0][A[0]] = V[0];
        for(i = 1; i < n; ++i)
        {
            for(j = m; j >= 0; --j)
            {
                if(dp[i-1][j] != -1)//上一行存在的状态
                {
                    dp[i][j] = dp[i-1][j];//不取物品
                    if(j+A[i] <= m)//取物品，且不超重
                        dp[i][j+A[i]] = max(dp[i][j+A[i]],dp[i-1][j]+V[i]);
                }
            }
        }
        return *max_element(dp[n-1].begin(),dp[n-1].end());
        //取最大的方案
    }
};