#动态规划 0-1背包问题空间复杂度优化

时间:2022-06-19 17:08:06

上一个版本的0-1背包代码的复杂度:时间复杂度O(n*C)空间复杂度O(n*C)

优化思路如下:

0-1背包问题:

F(n,C)考虑将n个物品放入背包为C 的背包,使得价值最大。

状态转移方程:F(i,c) = max(F(i-1 , c)  ,   v(i)+ F(i-1, c- w(i)  )

根据状态转移方程,第i行元素计算只依赖与i-1行元素。理论上我们只需要保持两行元素。

#动态规划 0-1背包问题空间复杂度优化

 

如上图,我们初始化后第一行存放0行元素,第二行存放1行元素。而第二行元素可以之间使用不再使用的0行元素。

#动态规划 0-1背包问题空间复杂度优化

发现规律:第一行一直为偶数行,第二行一直为奇数行,所以我们可以使用一个行数为2的二维数组来储存。

代码如下:

class Knapsack02{
    public int knapsack02(int[] w , int [] v, int C){
        assert(w.length == v.length && C>=0);

        int n = w.length;
        if(n == 0 || C==0)
            return 0;

        int[][] memo = new int[2][C+1];

        //第一行初始化。
        for(int i = 0 ; i<=C ; i++)
            memo[0][i] = (i>=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] = (int)Math.max(memo[i%2][j] , v[i]+memo[(i-1)%2][j-w[i]]);
            }
            
        return memo[(n-1)%2][C];    
    }

}

空间复杂度:O(2*C)

 

继续优化:

使用上一篇的例子,将其优化为两行。

#动态规划 0-1背包问题空间复杂度优化

 

发现dp[i][j] 只需要上一行的左边与上方的元素,而右边的元素并不需要。故尝试如下优化

#动态规划 0-1背包问题空间复杂度优化

我们仅仅使用一行元素记录。

#动态规划 0-1背包问题空间复杂度优化

更新位置5的元素,只需要位置3的元素以及自己(即上一种情况的上一行元素)即可。

 

 #动态规划 0-1背包问题空间复杂度优化

同理,更新位置4也仅仅需要自己当前元素以及位置2的元素。

#动态规划 0-1背包问题空间复杂度优化

 

 优化后数组为此。

我们仅仅需要一行元素,找到其对应的dp[j-v(i)]即可(物理意义为,掏空足够的空间,放入当前元素,选取不放入当前元素和放入的较大值)。

 

代码实现如下:

class Knapsack03{
    public int knapsack03(int[] w , int [] v, int C) {
        assert (w.length == v.length && C >= 0);

        int n = w.length;
        if (n == 0 || C == 0)
            return 0;

        int[] memo = new int[C + 1];

        //第一行初始化。
        for (int i = 0; i <= C; i++)
            memo[i] = (i >= w[0] ? v[0] : 0);

        for (int i = 1; i < n; i++)
            for (int j = C; j >= w[i]; j++) {
                memo[j] = (int) Math.max(memo[j], v[i] + memo[j - w[i]]);

           
            }
        return memo[C];
    }
}