[LintCode] Backpack II

Given n items with size A[i] and value V[i], and a backpack with size m. What's the maximum value can you put into the backpack?

Example

Given 4 items with size [2, 3, 5, 7] and value [1, 5, 2, 4], and a backpack with size 10. The maximum value is 9.

Note

You cannot divide item into small pieces and the total size of items you choose should smaller or equal to m

Update:

We can save the possible size, while the max value of an impossible size should be the max of values of possible sizes.

Analysis: just like Backpack 1, we just need record the weights for possible sizes.

class Solution {
public:
    int backPackII(int m, vector<int> A, vector<int> V) {
        int len = A.size();
        int maxV = 0;
        vector<int> weight(m+1,0);
        for (int i=0;i<len;i++)
        {
            for (int j=m;j>=A[i];j--)
            {
                weight[j] = max(V[i]+weight[j-A[i]], weight[j]);
                maxV = max(maxV, weight[j]);
            }
        }
        return weight[m];
    }
};