一层一层剥开背包问题

背包问题是非常经典的动态规划问题，这里设计到空间开销的问题，以下对方法不绝改进，优化空间开销。
1.记忆化搜索

时间复杂度: O(n * C) 此中n为物品个数; C为背包涵积
空间复杂度: O(n * C)

1. #include #include #include using namespace std;/// 背包问题/// 记忆化搜索/// 时间复杂度: O(n * C) 此中n为物品个数; C为背包涵积/// 空间复杂度: O(n * C)class Knapsack01{private:    vector memo;    // 用 [0...index]的物品,填充容积为c的背包的最大代价    int bestValue(const vector &w, const vector &v, int index, int c){        if(c = w[index])            res = max(res, v[index] + bestValue(w, v, index - 1, c - w[index]));        memo[index][c] = res;        return res;    }public:    int knapsack01(const vector &w, const vector &v, int C){        assert(w.size() == v.size() && C >= 0);        int n = w.size();        if(n == 0 || C == 0)            return 0;        memo.clear();        for(int i = 0 ; i < n ; i ++)            memo.push_back(vector(C + 1, -1));        return bestValue(w, v, n - 1, C);    }};

复制代码

• 动态规划
  时间复杂度: O(n * C) 此中n为物品个数; C为背包涵积
  空间复杂度: O(n * C)
  

1. #include #include #include using namespace std;/// 背包问题/// 动态规划/// 时间复杂度: O(n * C) 此中n为物品个数; C为背包涵积/// 空间复杂度: O(n * C)class Knapsack01{public:    int knapsack01(const vector &w, const vector &v, int C){        assert(w.size() == v.size() && C >= 0);        int n = w.size();        if(n == 0 || C == 0)            return 0;        vector memo(n, vector(C + 1,0));        for(int j = 0 ; j = w[0] ? v[0] : 0 );        for(int i = 1 ; i < n ; i ++)            for(int j = 0 ; j = w[i])                    memo[i][j] = max(memo[i][j], v[i] + memo[i - 1][j - w[i]]);            }        return memo[n - 1][C];    }};

复制代码

3.动态规划改进: 滚动数组
时间复杂度: O(n * C) 此中n为物品个数; C为背包涵积
空间复杂度: O©, 实际使用了2*C的额外空间

1. #include #include #include using namespace std;/// 背包问题/// 动态规划改进: 滚动数组/// 时间复杂度: O(n * C) 此中n为物品个数; C为背包涵积/// 空间复杂度: O(C), 实际使用了2*C的额外空间class Knapsack01{public:    int knapsack01(const vector &w, const vector &v, int C){        assert(w.size() == v.size() && C >= 0);        int n = w.size();        if( n == 0 && C == 0 )            return 0;        vector memo(2, vector(C + 1, 0));        for(int j = 0 ; j = w[0] ? v[0] : 0);        for(int i = 1 ; i < n ; i ++)            for(int j = 0 ; j = w[i])                    memo[i % 2][j] = max(memo[i % 2][j], v[i] + memo[(i-1) % 2][j - w[i]]);            }        return memo[(n-1) % 2][C];    }};

复制代码

4.动态规划改进
时间复杂度: O(n * C) 此中n为物品个数; C为背包涵积
空间复杂度: O©, 只使用了C的额外空间

1. public:    int knapsack01(const vector &w, const vector &v, int C){        assert(w.size() == v.size() && C >= 0);        intn = w.size();        if(n == 0 || C == 0)            return 0;        vector memo(C+1,0);        for(int j = 0 ; j = w[0] ? v[0] : 0);        for(int i = 1 ; i < n ; i ++)            for(int j = C ; j >= w[i] ; j --)                memo[j] = max(memo[j], v[i] + memo[j - w[i]]);        return memo[C];    }};

复制代码

来源：https://blog.csdn.net/weixin_38246633/article/details/85985991
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！