backpack 4 (lintcode 562)

图片.png

注意特例：

图片.png

图片.png

//my
///i562
class Solution {
public:
    int backPackIV(vector<int> &A, int m) {
        int ss = A.size();
        vector<vector<int>> dp(ss + 1, vector<int>(m + 1, 0));

        dp[0][0] = 1;
        for (int i = 1; i <= ss; i++) {
            for (int j = 0; j <= m; j++) {
                int k = 0;
                while (k * A[i - 1] <= j) {
                    dp[i][j] += dp[i - 1][j - A[i - 1] * k];
                    k += 1;
                }
            } // for j
        } // for i    
        return dp[ss][m];
    }
};