背包问题-三种动态规划解法-逐步减少空间复杂度

心已赠人 2021-12-16 14:55 142阅读 0赞

题目描述：有编号分别为1,2,3,4,5的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？

背包问题是典型的动态规划问题，也有一定的规律可循，通常采用自底向上的方式，先解决小问题，并存储，再解决大问题。

方法一：时间空间都为O(n^2)的解法，但可以得到最大价值情况下拿了哪些东西

这里dp\[i\]\[j\]的含义是：在只有i个物品，最大容量为j时，能获得的最大价值

def bag(weight, value, max_W):
        N = len(weight)
        V = max_W
        dp = [[0 for i in range(V+1)] for j in range(N+1)]
    
        for i in range(1,N+1):
            for j in range(1,V+1):
                if weight[i-1]<=j:
                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i-1]]+value[i-1])
                else:
                    dp[i][j] = dp[i-1][j]
        for i in range(N+1):
            print(dp[i][:])
        return dp
    
    def thing(weight,value,max_W,dp):	# 找出具体选了那些物品，这个可以参考第一个链接
        N = len(weight)
        V = max_W
        thing_flag = [0 for i in range(N)]
        j = V
        for i in range(N,0,-1):
            if dp[i][j] != dp[i-1][j]:
                thing_flag[i-1]=1
                j -= weight[i-1]
        print(thing_flag)
    
    weight = [2,2,6,5,4]
    value = [6,3,5,4,6]
    max_W = 10
    dp = bag(weight, value, max_W)
    thing(weight,value,max_W,dp)

这个例子中对应的dp矩阵如下所示

![SouthEast][]

可以通过从右下角向上回溯得到所有拿了的物品，见thing函数。

图片参考自：[https://blog.csdn.net/superzzx0920/article/details/72178544][https_blog.csdn.net_superzzx0920_article_details_72178544]

方法二：时间为O(n^2)，空间为O(2n)的解法

如果不需要求出具体选了哪些物品而只要最大价值，那在空间上还可以继续优化，因为我们求解dp\[i\]时，只用到了上一个子问题dp\[i-1\]，所以存储两个一维数组即可。

def bag(weight, value, max_W):
        N = len(weight)
        V = max_W
        dp = [0 for i in range(V)]
        dp_next = [0 for i in range(V)]
        for i in range(N):
            for j in range(V):
                if weight[i]<=j:
                    dp_next[j] = max(dp[j],dp[j-weight[i]]+value[i])
            dp = dp_next.copy()	#注意这里要用.copy()，因为不用就是浅复制
        print(dp_next)
        return dp

方法三：时间为O(n^2)，空间为O(n)的解法

再进一步思考，计算dp\[i\]\[j\]时只使用了dp\[i-1\]\[0……j\]，没有使用dp\[i-1\]\[j+1\]这样的话，我们先计算 j 的循环时，让j=V……1，即反方向计算，只使用一个一维数组即可。

def bag(weight, value, max_W):
        N = len(weight)
        V = max_W
        dp = [0 for i in range(V)]
        for i in range(N):
            for j in range(V-1,-1,-1):
                if weight[i]<=j:
                    dp[j] = max(dp[j],dp[j-weight[i]]+value[i])
        print(dp)
        return dp

[SouthEast]: /images/20211214/787c6c9615d64cacb90fccb6ce513fee.png
[https_blog.csdn.net_superzzx0920_article_details_72178544]: https://blog.csdn.net/superzzx0920/article/details/72178544