Given n items with size A[i], an integer m denotes the size of a backpack. How full you can fill this backpack?
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.
Note
Analysis:
You can not divide any item into small pieces.
We can say all the possible sums that are smaller than m. The biggest one is the result.
class Solution { public: int backPack(int m, vector<int> A) { // write your code here int len = A.size(); vector<bool> size(m+1,false); size[0] = true; for (int i=0;i<len;i++) { for (int j=m;j>=A[i];j--) { if (size[j-A[i]]) size[j] = true; } } int i = m; while(!size[i]) i--; return i; } };