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

素颜马尾好姑娘i 2022-10-27 12:06 186阅读 0赞

#  #

给出 n 个物品, 以及一个数组, `nums[i]` 代表第i个物品的大小, 保证大小均为正数, 正整数 `target` 表示背包的大小, 找到能填满背包的方案数。  
`每一个物品只能使用一次`

给出候选物品集合 `[1,2,3,3,7]` 以及 target `7`

结果的集合为:
    [7]
    [1,3,3]

返回 `2`

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

从题目的提问方式可以看出是属于典型的计数类型的动态规划。

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

需要知道N个物品有多少种方式拼出重量W (W =0, 1, …, Target)

最后一步：第N个物品（重量AN-1 ）是否进入背包。可以分为两种情况。

情况一：用前N-1个物品拼出W

情况二：用前N-1个物品能拼出W- AN-1 ，再加上最后的物品AN-1 ，拼出W

**情况一的个数+情况二的个数 =用前N个物品拼出W的方式**

因此我们可以假设状态f\[i\]\[w\]表示用前i个物品有多少种方式拼出重量w

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

假设状态f\[i\]\[w\]表示用前i个物品有多少种方式拼出重量w

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

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

初始条件：

f\[0\]\[0\]=1：0个物品可以有一种方式拼出重量0

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

边界情况：

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

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

逐行计算。答案f\[N\]\[Traget\]

时间复杂度：O(N\*Target)，空间复杂度：O(Target)

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

class Solution:
        """ @param nums: an integer array and all positive numbers @param target: An integer @return: An integer """
        def backPackV(self, nums, target):
            # write your code here
            if target == 0 or len(nums) == 0:
                return 0
            n = len(nums)
            #使用二维数组的话运行内存超出
            # dp=[[0]*(target+1) for i in range(n+1)]
            # dp[0][0]=1
            dp = [0] * (target + 1)
            dp[0] = 1
            for i in range(1, n + 1):
                for j in range(target, -1, -1):
                    if j >= nums[i - 1]:
                        dp[j] += dp[j - nums[i - 1]]
                    else:
                        break
            return dp[target]

#  #

[20210203221150134.png]: /images/20221024/f9cfcc4445b643c6ad6722212f8dfe0e.png