欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

一层一层剥开背包问题

程序员文章站 2022-06-22 17:33:13
背包问题是非常经典的动态规划问题,这里设计到空间开销的问题,以下对方法不断改进,优化空间开销。1.记忆化搜索时间复杂度: O(n * C) 其中n为物品个数; C为背包容积空间复杂度: O(n * C)#include <iostream>#include <vector>#include <cassert>using namespace std......

背包问题是非常经典的动态规划问题,这里设计到空间开销的问题,以下对方法不断改进,优化空间开销。

1.记忆化搜索

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

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// 背包问题
/// 记忆化搜索
/// 时间复杂度: O(n * C) 其中n为物品个数; C为背包容积
/// 空间复杂度: O(n * C)
class Knapsack01{

private:
    vector<vector<int>> memo;

    // 用 [0...index]的物品,填充容积为c的背包的最大价值
    int bestValue(const vector<int> &w, const vector<int> &v, int index, int c){

        if(c <= 0 || index < 0)
            return 0;

        if(memo[index][c] != -1)
            return memo[index][c];

        int res = bestValue(w, v, index-1, 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<int> &w, const vector<int> &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<int>(C + 1, -1));
        return bestValue(w, v, n - 1, C);
    }
};
  1. 动态规划
    时间复杂度: O(n * C) 其中n为物品个数; C为背包容积
    空间复杂度: O(n * C)
#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// 背包问题
/// 动态规划
/// 时间复杂度: O(n * C) 其中n为物品个数; C为背包容积
/// 空间复杂度: O(n * C)
class Knapsack01{

public:
    int knapsack01(const vector<int> &w, const vector<int> &v, int C){
        assert(w.size() == v.size() && C >= 0);
        int n = w.size();
        if(n == 0 || C == 0)
            return 0;

        vector<vector<int>> memo(n, vector<int>(C + 1,0));

        for(int j = 0 ; j <= C ; j ++)
            memo[0][j] = (j >= w[0] ? v[0] : 0 );

        for(int i = 1 ; i < n ; i ++)
            for(int j = 0 ; j <= C ; j ++){
                memo[i][j] = memo[i-1][j];
                if(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的额外空间

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// 背包问题
/// 动态规划改进: 滚动数组
/// 时间复杂度: O(n * C) 其中n为物品个数; C为背包容积
/// 空间复杂度: O(C), 实际使用了2*C的额外空间
class Knapsack01{

public:
    int knapsack01(const vector<int> &w, const vector<int> &v, int C){
        assert(w.size() == v.size() && C >= 0);
        int n = w.size();
        if( n == 0 && C == 0 )
            return 0;

        vector<vector<int>> memo(2, vector<int>(C + 1, 0));

        for(int j = 0 ; j <= C ; j ++)
            memo[0][j] = (j >= w[0] ? v[0] : 0);

        for(int i = 1 ; i < n ; i ++)
            for(int j = 0 ; j <= C ; j ++){
                memo[i % 2][j] = memo[(i-1) % 2][j];
                if(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的额外空间

public:
    int knapsack01(const vector<int> &w, const vector<int> &v, int C){
        assert(w.size() == v.size() && C >= 0);
        intn = w.size();
        if(n == 0 || C == 0)
            return 0;

        vector<int> memo(C+1,0);

        for(int j = 0 ; j <= C ; j ++)
            memo[j] = (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