Backpack

Given_n_items with size Ai, an integer_m_denotes the size of a backpack. How full you can fill this backpack?
Example

If we have4items with size[2, 3, 5, 7], the backpack size is 11, we can select[2, 3, 5], so that the max size we can fill this backpack is10. If the backpack size is12. 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.

S: 背包类DP，以值作为dp维度 O(mn)

dp[i][j]表示从0-i是否可组成大小为j的背包。因为只要dp[i-1][j]可以取到，dp[i][j]就一定能取到，所以可以用一维数组存储dp结果

    int backPack(int m, vector<int> A) {
        int n = A.size();
        if (n < 1) return 0;
        vector<bool> dp(m + 1, false);
        dp[0] = true;
        for (int i = 0; i < n; ++i) {
            for (int j = m; j >= A[i]; --j) {
                dp[j] = dp[j] || dp[j-A[i]];
            }
        }
        for (int j = m; j >= 0; --j) {
            if (dp[j]) {
                return j;
            }
        }
        return 0;
    }