class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    int backPack(int m, vector<int> A) {
        // table[i][j] denotes whether using the first elements
        // could fulfill size j.
        vector<vector<bool>> dp(A.size() + 1, vector<bool>(m + 1, false));
        if(m == 0 || A.size() == 0) {
            return 0;
        }
        for(int i = 0; i < m + 1; i++)   dp[0][i] = false;
        
        for(int i = 0; i < A.size() + 1; i++)  dp[i][0] = true;
        
        for(int i = 1; i < A.size() + 1; i++) {
            for(int j = 1; j < m + 1; j++) {
                if(j - A[i-1] < 0) {
                    dp[i][j] = dp[i - 1][j];
                }
                else {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - A[i - 1]];
                }
            }
        }
        
        for(int i = m; i >= 0; i--) {
            if (dp[A.size()][i]) {
                return i;
            }
        }
        return 0;
    }
};

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
        vector<vector<int>> dp(A.size() + 1, vector<int>(m + 1, false));
        if(m == 0 || A.size() == 0) {
            return 0;
        }
        
        for(int i = 0; i < m + 1; i++)   dp[0][i] = 0;
        for(int i = 0; i < A.size() + 1; i++)  dp[i][0] = 0;
        
        for(int i = 1; i < A.size() + 1; i++) {
            for(int j = 1; j < m + 1; j++) {
                if(j - A[i-1] < 0) {
                    dp[i][j] = dp[i - 1][j];
                }
                else {
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - A[i - 1]] + V[i - 1]);
                }
            }
        }
        
        return dp[A.size()][m];
    }
};

class Solution {
public:
    /**
     * @param nums an integer array and all positive numbers, no duplicates
     * @param target an integer
     * @return an integer
     */
    int backPackVI(vector<int>& nums, int target) {
        vector<int> dp(target + 1);
        dp[0] = 1;
        for (int i = 1; i <= target; ++i) {
            for (const auto& num : nums) {
                if (i >= num) {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp.back();
    }
};