LintCode: Backpack

Given n items with size A[i], an integer m denotes the size of a backpack. How full you can fill this backpack?

Note

You can not divide any item into small pieces.

Example

If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select 2, 3 and 5, so that the max size we can fill this backpack is 10. If the backpack size is 12. we can select [2, 3, 7] so that we can fulfill the backpack.
You function should return the max size we can fill in the given backpack.

 
class Solution {
public:
     int backPack(int m, vector<int> A) {
        int n = A.size();
        vector<bool> canFill(m+1, false);
       
        canFill[0] = true;
       
        for(int i = 0; i < n; i++)
        {
            for(int j = m; j>= A[i]; j--)
                canFill[j] = canFill[j] || canFill[j-A[i]] ;
        }
       
        for(int i = m; i >=0; i--)
           if (canFill[i]) return i;
       
        return 0;
    }
};