C++动态规划dp算法题(3)

class Backpack {
public:
    int maxValue(vector<int> w, vector<int> v, int n, int cap) {
        if (w.empty()||v.empty()||n==0||cap==0)
            return 0;
        vector<vector<int> > dp(n,vector<int>(cap+1));
         
        for (int j = 1;j < cap+1;j++) {
            dp[0][j] = w[0] <= j?v[0]:0;
        }
        for (int i = 0;i < n;i++) {
            dp[i][0] = 0;
        }
         
        for (int i = 1;i < n;i++) {
            for (int j = 1;j < cap+1;j++) {
                if (w[i] > j)
                    dp[i][j] = dp[i-1][j];
                else
                    dp[i][j] = max(dp[i-1][j],v[i]+dp[i-1][j-w[i]]); //由于该问题每个物品最多只能放1件，如果不限制个数的话，则在这里修改条件
            }
        }
        return dp[n-1][cap];
    }
};

由于没有用到斜侧的比较，所以可以使用1维的数组：

class Backpack {
public:
    int maxValue(vector<int> w, vector<int> v, int n, int cap) {
        if (w.empty()||v.empty()||n==0||cap==0)
            return 0;
        vector<int> dp(cap+1,0);       
        for (int i = 0;i < n;i++) {
            vector<int> last(dp);
            for (int j = 1;j < cap+1;j++) {
                dp[j] = j < w[i]?last[j]:max(last[j],v[i]+last[j-w[i]]);               
            }
        }
        return dp[cap];
    }
};

Linux公社的RSS地址：https://www.linuxidc.com/rssFeed.aspx