Backpack II 背包问题

Given n items with size Ai and value Vi, and a backpack with size m. What's the maximum value can you put into the backpack?

Solution

跟背包问题I一样，只是加了权重

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

滚动数组 + 自底向上动规

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