Backpack II

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

Note

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

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.

 
class Solution {
public:
 
    /**
     * @param W: 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 W, vector<int> A, vector<int> V) {
    
        /*
         The 0/1 knapsack problem also runs in pseudo-polynomial time.
         Define m[i,w] to be the maximum value that can be attained with
         weight less than or equal to w using items up to i (first i items).
         We can define m[i,w] recursively as follows:
           m[i, w] = m[i-1,w]                       if w less than A[i]
           m[i, w] = max(m[i-1,w],m[i-1,w-w_i]+v_i) if w equal to greater than A[i].
         The solution can then be found by calculating m[n,W]. T 
       */
    
        vector<int> m(W+1, 0);
        for( int i = 0; i < A.size(); i++) 
           for(int j = W; j > 0; j--) {
              if (j >= A[i]) m[j] = max(m[j], m[j-A[i]] + V[i]);
        }
        
        return m[W];
    }
};