8.Backpack II

http://www.lintcode.com/zh-cn/problem/backpack-ii/

class Solution {
public:
    /**
     * @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
        int n = A.size();
        vector<int> f(m + 1, 0);
        for (int k = 0; k < n; k++) {
            for (int i = m; i >= A[k]; i--) {
                if (f[i-A[k]] + V[k] > f[i]) {
                    f[i] = f[i-A[k]] + V[k];
                }
            }
        }
        return f[m];
    }
};