请选择 进入手机版 | 继续访问电脑版

一层一层剥开背包问题

[复制链接]
丶禁飞 发表于 2021-1-1 10:32:30 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
背包问题是非常经典的动态规划问题,这里设计到空间开销的问题,以下对方法不绝改进,优化空间开销。
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
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )