LintCode 1915. 举重（01背包）

class Solution {
public:
    /**
     * @param weights: An array of n integers, where the value of each element weights[i] is the weight of each plate i
     * @param maxCapacity: An integer, the capacity of the barbell
     * @return: an integer denoting the maximum capacity of items that she can lift.
     */
    int weightCapacity(vector<int> &weights, int maxCapacity) {
        // Write your code here
        int n = weights.size();
        vector<bool> dp(maxCapacity+1, false);
        dp[0] = true;
        int maxW = 0;
        for(int i = 0; i < n; ++i)
        {
            for(int j = maxCapacity-weights[i]; j>=0; --j)
            {	//逆序遍历，新状态不会干扰前面待遍历的旧状态
                if(dp[j])// j 重量状态存在
                {
                    dp[j+weights[i]] = true;
                    maxW = max(maxW, j+weights[i]);
                }
            }
        }
        return maxW;
    }
};