【算法学习】01背包问题_背包时间复杂度

来源是慕课网的实战算法课程——动态规划

01背包问题

相当于还是求n个物品的组合！
暴力解法：
每一件物品，都可以放进背包，也可以不放进。复杂度是O( (2^n) * n )， 对于每一个组合，还要看看对应的总重是多少，看看是不是超过了容量C，从而看价值。

组合方式都可以用递归的方式来求解。只是是能不能找到重叠子问题、最优子结构，从而转换为DP。

设计：
状态：之前状态都使用一个参数就解决了问题，通常问题中参数的个数意味着要解决问题需要满足的约束条件。
这个问题2个约束条件，首先要从n个物品里选，然后容量要满足≤C，因此：状态（函数）是
F(n,C)考虑将n个物品放入容量为C的背包，使得价值最大。

状态转移：F( i,c) = F(i-1,c)
= v(i) + F( i-1, c-w(i) ) 放入后，考虑前面i-1个物品
对于第i个物品到底要放入or不放入背包，在二者中选一个max
状态转移方程：F(i,c) = max( F(i-1,c), v(i) + F( i-1, c-w(i) ) )
很多动态规划问题都可以使用类似上面的思想！

写代码：依旧先使用自顶向下，再改造为自底向上
递归方式：

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

        // 无法选物品 or 装不下物品，都无价值
        if(index < 0 || c<=0)  
            return 0;

        int res = bestValue( w, v, index-1, c);
        // 检查一下容积C
        if( c >= w[index])
            res = max(res, v[index] + bestValue(w,v,index-1, c-w[index]) );

        return res;
    }

public:
    int knapsack01(const vector<int> &w, const vector<int> &v, int C ){

        int n = w.size();

        return bestValue(w, v, n-1, C); //考虑从0-n-1的n个物品，装入C
    }
    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

用记忆化搜索+递归：

重叠子问题：index 和c构成了数据对，这样的数据对在求解过程中同样的数据对可能求解了多次，为此可以使用记忆化搜索方式。
由于背包问题有两个约束条件，每一个状态中被2个变量定义，所以开辟记忆化空间是二维数组！—— vector<vector> memo(n, vector(C+1, -1));
memo有n行，每一行都是一个vector，一共有C+1列

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

        // 先判断有无值
        if(memo[index][c] != -1)
            return memo[index][c];

        // 无法选物品 or 装不下物品，都无价值
        if(index < 0 || c<=0)  
            return 0;

        for(int i=, i>=0; --i)
            for( int j=1; j<c; ++j ){
                memo[i] + ;
            }

        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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

动态规划：

int knapsack01(const vector<int> &w, const vector<int> &v, int C ){

        assert(v.zise() == w.size()); // 判断一下
        int n = w.size();
        if(n==0)
            return 0;

        memo = vector<vector<int>>(n, vector<int>(C+1, -1)); //memo有n行，每一行都是一个vector<int>，一共有C+1列

        for(int j=0; j<=C; ++j)
            memo[0][j] = ( j >= w[0] ? v[0] : 0 );  //j是此时背包的容量
        
        for(int i=1; i<n; ++i)
            for(int j=0; j<=C; ++j){  

                memo[i][j] = memo[i-1][j];
                if( w[i] <= j )  // 可用容量大
                    memo[i][j] = max(memo[i][j], v[i]+memo[i-1][j-w[i] ] );
            }

        return memo[n-1][C];
    }
    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

01背包复杂度：
时间复杂度：O(nC)
空间复杂度：O(nC)
优化空间：时间上很小，空间上有很大的优化空间~

01背包问题的优化：
状态转移方程：F(i,c) = max( F(i-1,c), v(i) + F( i-1, c-w(i) ) )
第i行元素只依赖于第i-1行元素。理论上，只需要保持两行元素。因此空间复杂度变为：O(2*C) ≈O( C )

上面行处理偶数，下面行处理奇数。

int knapsack01(const vector<int> &w, const vector<int> &v, int C ){

        assert(v.zise() == w.size()); // 判断一下
        int n = w.size();
        if(n==0)
            return 0;

        memo = vector<vector<int>>(2, vector<int>(C+1, -1)); //memo有n行，每一行都是一个vector<int>，一共有C+1列

        for(int j=0; j<=C; ++j)
            memo[0][j] = ( j >= w[0] ? v[0] : 0 );  //j是此时背包的容量
        
        for(int i=1; i<n; ++i)
            for(int j=0; j<=C; ++j){  

                memo[i%2][j] = memo[(i-1)%2][j];
                if( w[i] <= j )  // 可用容量大
                    memo[i%2][j] = max(memo[i%2][j], v[i]+memo[(i-1)%2][j-w[i] ] );
            }

        return memo[(n-1)%2][C];
    }
    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

进一步优化！
使得只用一行大小为C的数组来完成DP

对于上一行：永远只使用上边和左边的元素，而不会去碰右边的元素！
因此，如果只有一行的话，只看当前值和之前的内容~ 从而只需要从右向左的来刷新内容~ 即从：C=5,4,…1,0
如果有一个格子，容量不足以装下当前的物品，则这个容量到之前的物品都不能放置了！都要使用原先的物品来放。从而这样算法还能提前终止一些，空间时间复杂度都可以降低一些~

int knapsack01(const vector<int> &w, const vector<int> &v, int C ){

        assert(v.zise() == w.size()); // 判断一下
        int n = w.size();
        if(n==0)
            return 0;

        vector<int> memo(C+1, -1); //memo有n行，每一行都是一个vector<int>，一共有C+1列

        for(int j=0; j<=C; ++j)
            memo[j] = ( j >= w[0] ? v[0] : 0 );  //j是此时背包的容量
        
        for(int i=1; i<n; ++i)
            for(int j=C; j>=w[i]; --j){   // 条件是j>w[i]
                  // 可用容量大
                memo[j] = max(memo[j], v[i] + memo[j-w[i]] );
            }

        return memo[C];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

01背包的变种：
完全背包问题：每个物品可以无限使用~
（虽然每个物品可以无限使用，但是背包容量有限，所以其实每个物品可以取到的个数是有最大值的！
===>所以把无限使用的物品背包问题转换为有点使用物品的背包问题~， 只是在选取的物品列表中有很多物品是重复的）
优化方案：（对于背包容积很大的时候很好的优化思路）对于任何一个数字而言，都可以用一个二进制码来表示，所以对于同一个物品，不一定向列表中添加1，而是添加1 2 4 8 16这样的序列，表示同一个物品取了多少个。

多重背包：每个物品不止一个，有num(i)个
多重背包是更简单的

多为费用背包问题：要考虑物品的体积和重量两个维度！（也就是用三维数组）
物品加入更多约束：物品之间可以互相排斥；也可以互相依赖