92. Backpack

Code(Language:C++) (Judger:cloudjudge-cluster-5)

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) {
        // write your code here
        vector<int> dp(m + 1, 0);
        dp[0] = 1; 
        for(int i = 0; i < A.size(); i++){
            for(int j = m; j >= A[i]; j--){
            //for(int j = A[i]; j <= m; j++){ //记住这里反向，没想明白为什么
                dp[j] = dp[j] || dp[j - A[i]]; 
            }
        }
        for(int i = m; i >= 0; i--){
            if(dp[i]){
                return i; 
            }
        }
    }
};