背包型动态规划——背包问题1

旧城等待， 2022-10-27 06:30 174阅读 0赞

#  #

在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A\[i\]

示例：

样例 1:
    	输入:  [3,4,8,5], backpack size=10
    	输出:  9
    
    样例 2:
    	输入:  [2,3,5,7], backpack size=12
    	输出:  12

### 1、题目分析 ###

首先要明确一点，在背包问题中，数组大小和总称重有关。

给定N个物品，重量分别为正整数A0, A1, …, AN-1。一个背包最大承重是M，物品的重量都是整数。每个装物品的方案的总重量都是0到M。如果对于每个总重量，我们能知道有没有方案能做到，就可以解决。

### 2、确定状态 ###

需要知道N个物品是否能拼出重量W（W=0，1……）。最后一步：最后一个物品是否进入背包。

情况1:如果前N-1个物品能够拼出W，那么前N个物品也能拼出W

情况2:如果前N-1个物品能拼出W-An-1，再加上最后的物品An-1,拼出W

![在这里插入图片描述][20210203220538348.png]

因此我们可以假设状态f\[i\]\[w\]表示能否用前i个物品拼出重量w

### 3、转移方程 ###

假设状态f\[i\]\[w\]表示能否用前i个物品拼出重量w  
![在这里插入图片描述][20210203220545160.png]

### 4、初始条件和边界情况 ###

初始条件：

f\[0\]\[0\]=True：0个物品可以拼出重量0

f\[0\]\[1……M\]=False：0个物品不能拼出大于0的重量

边界情况：

f\[i-1\]\[w-Ai-1\]只能在w>Ai-1时使用

### 5、计算顺序 ###

逐行计算，时间复杂度：O(MN)，空间复杂度：优化后 可以达到O(M)

### 6、代码实现 ###

class Solution:
        """ @param m: An integer m denotes the size of a backpack @param A: Given n items with size A[i] @return: The maximum size """
        def backPack(self, m, A):
            # write your code here
            if m==0 or len(A)==0:
                return 0
            dp=[[False]*(m+1) for i in range(len(A)+1)]
            dp[0][0]=True
            for i in range(1,len(A)+1):
                for j in range(m+1):
                    dp[i][j]=dp[i-1][j]
                    if j>=A[i-1]:
                        dp[i][j]=dp[i][j] or dp[i-1][j-A[i-1]]
            res=0
            for i in range(m,-1,-1):
                if dp[len(A)][i]==True:
                    res=i
                    break
            return res
    
            #下面的方法是采用滚动数组去优化，我之前一直没搞懂为什么要逆序，后面才知道举个例子假设我们要计算F ( i , 4 ) F(i,4)F(i,4),我们需要用到的值为F ( i − 1 , 4 ) F(i-1,4)F(i−1,4)和F ( i − 1 , 4 − w ( i ) ) F(i-1,4-w(i))F(i−1,4−w(i)),因此为了防止结果被覆盖，我们需要从后向前依次计算结果
            if m==0:
                return 0
            n=len(A)
            dp=[0]*(m+1)
            for i in range(1,n+1):
                for j in range(m,-1,-1):#逆序
                    if j>=A[i-1]:
                        dp[j]=max(dp[j],dp[j-A[i-1]]+A[i-1])
                    else:
                        break
            print(dp)
            return dp[m]

#  #

[20210203220538348.png]: /images/20221024/3077f1c5e0044b51bc9b2a481c944b38.png
[20210203220545160.png]: /images/20221024/3422e340bd04480d9af37db992e0d58c.png