《动态规划》：01背包、完全背包、多重背包、01背包组合、完全背包组合&排列问题

 
 学习之前建议收听音乐：你的背包????~

⭐????⭐背包问题一般模板：

【注：这个一般性模板作为一个总结的东西，先把后面背包问题理解了再来看就清晰很多。当然有时候模版公式要根据实际问题修改】
 
1️⃣内外循环分类：

类型	模板
01背包问题	外循环nums,内循环target,target倒序且target>=nums[i]; 【注：01背包内外循环不能颠倒（不过用二维的dp数组的话倒是可以逆序和颠倒）】
01背包组合问题	外循环nums,内循环target,target倒序且target>=nums[i];【注：01背包内外循环不能颠倒】
纯完全背包问题	外循环nums,内循环target,target正序且target>=nums[i];【注：完全背包内外循环可以颠倒，for循环做点小修改即可。公式不变（用二维的dp数组的话正序。也可以颠倒）】
完全背包组合问题	外循环nums,内循环target,target正序且target>=nums[i];【注：完全背包组合问题内外循环不能颠倒】
完全背包排列问题	外循环target,内循环nums,target正序且target>=nums[i];【注：完全背包排列问题内外循环不能颠倒】

2️⃣问题分类：

类型	模板
最值问题	dp[j] = max/min(dp[j], dp[j-nums[i]]+1) 或 dp[j] = max/min(dp[j], dp[j-nums[i]]+nums[i]);
存在问题	dp[j] = dp[j] or dp[j-nums[i]];
组合 or 排列问题	dp[j] += dp[j-nums[i]]

 
 

⭐以下关于各背包问题的具体解释都在代码注释中。

难度
一、01背包问题
二、完全背包问题
三、多重背包问题
四、01背包存在问题
五、完全背包存在问题
六、01背包组合问题
七、完全背包组合问题
八、完全背包排列问题

 

????一、01背包问题：

 01背包可以说是其他背包问题的基础，一定要弄透彻！

 先来看一个二维dp数组的写法，具体解释看注释即可：
【注：下面是先遍历物品再遍历背包，这样会好理解点。当然先遍历背包，再遍历物品，也是可以的！因为从这两种情况的状态转移公式可以看出（两种情况状态转移公式是一样的，调换下for循环顺序而已），更新的数据都是来自正左和正上方向。当然在一些背包问题里，两个for循环的先后循序是非常常有讲究的】

def bag_01_2D():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bag_weight = 4

    #状态定义:dp[i][j]表示从0-i 个 物品中选择不超过j重量的物品的最大价值
    #注意python中二维数组的创建方式
    dp = [[0]*(bag_weight+1) for _ in range(len(weight)+1)]

    #边界：
    # 第一列都是0，因为价值为0(因为初始化全部为0了这里就不用了)，
    # 第一行表示只选取0号物品最大价值(要满足背包容量放⾜够放编号0物品)
    for j in range(bag_weight, weight[0]-1, -1):
        dp[0][j] = dp[0][j - weight[0]]+value[0]

    #外循环遍历物品
    for i in range(1, len(weight)):
        #内循环遍历背包容量
        for j in range(0, bag_weight+1):
            # 背包容量放不下第i个物品
            if j < weight[i]:
                dp[i][j] = dp[i-1][j]

            # 背包容量放的下第i个物品，可放可不放
            # 不放：那就等于前i-1个物品（在容量j中）的最大价值
            # 放：那就等于前i-1个物品（在容量j-weight[i]中）的最大价值+第i个物品的价值
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])

    return dp[len(weight)-1][bag_weight]

• 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
• 28
• 29
• 30

【dp[i-1][j-weight[i]]+value[i]意思就是：在重量为j时包含了物品i，那肯定就要冲重量j-weight[i]转移过啊来咯。】
 因为从状态转移方程可以清晰看到 i 时刻只与上一时刻 i-1 相关。所以可以用一维数组取代二维数组进行滚动即可。后面其他两个背包问题都用一维数组，毕竟空间复杂度小。
 关于内循环逆序的例子解释（因为这样避免了正序时，前面的状态选了i物品，后面状态又基于它又选了i物品，而i物品只能选一次。所以逆序遍历可以保证只取一次物品）：

def bag_01():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bag_weight = 4

    # dp[j]表示容量为j的背包能放下东西的最大价值
    dp = [0]*(bag_weight+1)

    # 外循环遍历物品
    for i in range(0, len(weight)):
        # 内循环遍历背包容量，一定要逆序！！！这样可以保证物品i只被放入一次
        # 从二维那个公式中我们可以知道，当前时刻i只和i-1时刻的状态有关，
        # 如果正序的话那，在一维中更新当前时刻i的dp[j]时，dp[j-weight[i]]变成了当前的时刻i的更新的，而此时需要的是上一时刻i-1的dp[j-weight[i]]的旧值(得益于逆序遍历，后面的先更新)
        # 所以逆序可以避免dp[j-weight[i]]的旧值被更新先。
        for j in range(bag_weight, weight[i]-1, -1):
            #上面二维的做法中的：if j < weight[i]和else在这里合为了下面一句话，因为满足if时相当于等于i-1时刻的状态，在这里不变还是d[j]即i-1时的状态，所以可以不写。且for循环控制了j不会小于weight[i]，小于weight[i]的不用更新就好，沿用i-1时刻的就ok。
            #不放或放第i个物品
            #不放：则是取前i-1个物品时（在容量为j中）的最大价值
            #放：则是取前i-1个物品（在容量j-weight[i]中）的最大价值
            dp[j] = max(dp[j], dp[j-weight[i]]+value[i])

    return dp[bag_weight]

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22

 那么上面的两个内外for循环能否调换位置呢？（即先遍历背包容量再遍历物品？）
 答：肯定不能啦，因为背包容量的遍历是逆序的(这样d[j]的前面小于j的索引都是0啊，都还是初始化的状态)。看状态转移公式可以知道，这样一来，后果就是每个背包只放了一个物品哈哈哈。

 而二维不用逆序是因为：
 因为对于二维dp，dp[i][j]都是通过上⼀层即dp[i - 1][j]计算而来（因为i-1时并没有取i物品，之所以逆序就是避免当前层重复取了 i 物品），本层的dp[i][j]并不会被覆盖！

 

????二、完全背包问题：

 就是将01背包中的内循环改成正序遍历，即可实现每种物品可以选无限次。（至于为什么正序，弄懂了前面01背包的逆序讲解这个就很好懂了）：

# 状态定义:dp[i][j]表示从0-i 种 物品中选择不超过j重量的物品的最大价值

# 01背包中，状态转移为：max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])
# 而完全背包中，状态转移为：max(dp[i-1][j], dp[i][j-weight[i]]+value[i]),具体解释看下面


def bag_full():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bag_weight = 4

    # dp[j]表示容量为j的背包能放下物品的最大价值
    dp = [0]*(bag_weight+1)

    # 外循环遍历物品种类
    for i in range(0, len(weight)):
        #内循环遍历背包容量，正序，因为可以重复放
        for j in range(weight[i], bag_weight+1):

            # 背包容量放的下第i 种 物品，可放可不放
            # 不放：那就等于前i-1 种 物品（在容量j中）的最大价值
            # 放：那就等于前i 种 物品（在容量j-weight[i]中）的最大价值。
            # 选择放的时候，不取决与前一时刻的状态，因为前一时刻只包含i-1种物品，不包含第i种物品，所以不可能从i-1时刻转移过来。

            dp[j] = max(dp[j], dp[j-weight[i]]+value[i])

    return dp[bag_weight]

• 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

 再来2个灵魂拷问彻彻底底弄清完全背包。
 1.内外for循环的顺序能否颠倒？
 可以的无所谓，代码如下，状态转移方程不变。

	for j in range(0, bag_weight+1):
		for i in range(0, len(weight)):
			if weigth[i]<=j:
				dp[j] = max(dp[j], dp[j-weight[i]]+value[i])

• 1
• 2
• 3
• 4

 因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以咯，毕竟正序遍历，可以选无数次物品哈哈。

 2.用2维数组实现的话如何？
 01背包二维dp数组实现中，状态转移方程为：

# 背包容量放的下第i个物品，可放可不放
# 不放：那就等于前i-1个物品（在容量j中）的最大价值
# 放：那就等于前i-1个物品（在容量j-weight[i]中）的最大价值
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])

• 1
• 2
• 3
• 4

 完全背包二维数组实现中，将状态转移方程改为：

# 背包容量放的下第i 种 物品，可放可不放
# 不放：那就等于前i-1 种 物品（在容量j中）的最大价值
# 放：那就等于前i 种 物品（在容量j-weight[i]中）的最大价值。
#选择放的时候，不取决与前一时刻的状态，
#因为前一时刻只包含i-1 种 物品，不包含第i 种 物品，所以不可能从i-1时刻转移过来。
dp[i][j] = max(dp[i-1][j], dp[i][j-weight[i]]+value[i])

• 1
• 2
• 3
• 4
• 5
• 6

 听说那些变种题目，在这两个for循环顺序上会有很大区别，要注意题目稍有变换for循环顺序很关键。（因为这两个for循环的顺序的调换在一些问题上会涉及到组合或排列问题，所以有时不能调换，针对问题看情况。只有纯完全背包类型的问题才可以调换。）
 对于背包问题，递推公式算是容易的，难是难在遍历顺序上，如果把遍历顺序搞透，才算真正理清了。

 

????三、多重背包问题：

def bag_multi():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    limit = [2,2,1]
    bag_weight = 4

    # dp[j]表示容量为j的背包能放下物品的最大价值
    dp = [0]*(bag_weight+1)

    # 外循环遍历物品种类
    for i in range(0, len(weight)):
        # 内循环遍历背包容量,逆序，因为我将其看成了一个：01背包问题
        # 为何可以看出01背包问题。因为相当于我将每个种类里的物品进行了各种数量的捆绑后看出一个整体，只能选一次（当然前提是也不能超过背包容量：j）
        # 具体操作是在内层循环里开多一层循环，遍历每种满足条件的捆绑情况，看哪种捆绑情况价值最大。
        for j in range(bag_weight, weight[i]-1, -1):
            k=1
            while(k<=limit[i] and k*weight[i]<=j):
                dp[j] = max(dp[j], dp[j-k*weight[i]] + k*value[i])
                k += 1

    return dp[bag_weight]

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21

 还有一种时间复杂度一样但是空间会有点浪费的方法就是：
 将每个种类的物品都看成只能选1次的物品，扩展一下weight和value列表，然后就可以直接看成一个01背包问题了。
 然后还有一种用了二进制思想去优化时间复杂度的方法具体自己百度咯。因为听说leetcode上没有多重背包类型的题目，面试也会比较少出。基本都是01背包或完全背包的变种类型题目。

 

????四、01背包存在问题：

def bag_01_exist():
    weight = [1, 3, 4, 2, 2]
    bag_weight = 13

    # dp[j]能否刚好装满容量为j的背包
    dp = [False]*(bag_weight+1)
    # dp[j]都是依赖j以前的索引的dp值来更新的，若dp[0]=False。那整个dp数组都为False了。
    dp[0] = True

    # 外循环遍历物品
    for i in range(0, len(weight)):
        # 内循环遍历背包容量，逆序和01背包一样
        for j in range(bag_weight, weight[i]-1, -1):

            #在i-1状态时，dp[j]表示从前i-1个物品中选取物品是否能刚好装满容量为j的背包
            #dp[j-weight[i]]表示在背包容量为j-weight[i]时，从前i个物品中选取物品是否能刚好装满容量为j的背包。
            #所以将上面两种情况之一满足True，那肯定dp[j]为True
            dp[j] = dp[j] or dp[j-weight[i]]

    return dp[bag_weight]

print(bag_01_exist())

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22

 

????五、完全背包存在问题：

def bag_full_exist():
    weight = [3,11,12,15]
    bag_weight = 10

    # dp[j]能否刚好装满容量为j的背包
    dp = [False]*(bag_weight+1)
    # dp[j]都是依赖j以前的索引的dp值来更新的，若dp[0]=False。那整个dp数组都为False了。
    dp[0] = True

    # 外循环遍历每种物品
    for i in range(0, len(weight)):
        # 内循环遍历背包容量，正序
        for j in range(weight[i], bag_weight+1):

            #在i-1状态时，dp[j]表示从前i-1种物品中选取物品是否能刚好装满容量为j的背包
            #dp[j-weight[i]]表示在背包容量为j-weight[i]时，从前i种物品中选取物品是否能刚好装满容量为j的背包。
            #所以将上面两种情况之一满足True，那肯定dp[j]为True

            dp[j] = dp[j] or dp[j-weight[i]]
    return dp[bag_weight]

print(bag_full_exist())

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22

 

????六、01背包组合问题：

 也就是01背包问题的扩展，求装满背包的组合数。解释看代码即可：

def bag_01_combine():
    weight = [1, 3, 4, 2, 2]
    bag_weight = 4

    # dp[j]表示装满容量为j的背包一共有dp[j]种组合方法
    dp = [0]*(bag_weight+1)

    # 即背包容量为0，有1种方法即装0件。不能初始化为0毕竟从状态转移公式可见，
    # dp[j]都是依赖j以前的索引的dp值来更新的，若dp[0]=0。那整个dp数组都为0了。
    dp[0] = 1

    # 外循环遍历物品
    for i in range(0, len(weight)):
        # 内循环遍历背包容量，逆序和01背包一样
        for j in range(bag_weight, weight[i]-1, -1):

            #在i-1状态时，dp[j]表示从前i-1个物品中选取物品装满背包容量为j的组合数。当然我加上物品i后的组合数是不变的
            #dp[j-weight[i]]表示在背包容量为j-weight[i]时，从前i个物品中选取物品装满容量为j的背包的组合数。
            #所以将上面两个加起来就是下式，表示：在背包容量为j时的组合数等于，前i-1个物品的组合数（背包容量为j）加上从前i个物品中选取物品的组合数(背包容量为j-weight[i])
            dp[j] += dp[j-weight[i]]

    return dp[bag_weight]

print(bag_01_combine())

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24

 

????七、完全背包组合问题：

 弄懂01背包组合问题，这个很好懂，不过要注意了，求组合数的问题，内外2个for循环可不能颠倒，颠倒了就变成了求组合数或排列数问题，这是不一样的。要十分注意。

def bag_full_combine():
    weight = [1, 3, 4]
    bag_weight = 4

    # dp[j]表示装满容量为j的背包一共有dp[j]种组合方法
    dp = [0]*(bag_weight+1)

    # 即背包容量为0，有1种方法即装0件。不能初始化为0毕竟从状态转移公式可见，
    # dp[j]都是依赖j以前的索引的dp值来更新的，若dp[0]=0。那整个dp数组都为0了。
    dp[0] = 1

    # 外循环遍历每种物品
    for i in range(0, len(weight)):
        # 内循环遍历背包容量，正序
        for j in range(weight[i], bag_weight+1):

            #在i-1状态时，dp[j]表示从前i-1 种 物品中选取物品装满背包容量为j的组合数。当然我加上物品i后的组合数是不变的
            #dp[j-weight[i]]表示在背包容量为j-weight[i]时，从前i种物品中选取物品装满容量为j的背包的组合数。
            #所以将上面两个加起来就是下式，表示：在背包容量为j时的组合数等于，前i-1 种 物品的组合数（背包容量为j）加上从前 i 种物品中选取物品的组合数(背包容量为j-weight[i])

            dp[j] += dp[j-weight[i]]

    return dp[bag_weight]

print(bag_full_combine())

• 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

⭐下面解释下内外for循环的顺序问题：

 因为先遍历物品再遍历背包，就是组合问题：

for i in range(0, len(weight)):
	for j in range(weight[i], bag_weight+1):
		dp[j] += dp[j-weight[i]]

• 1
• 2
• 3

 假设有两个物品：weight[0] = 1，weight[1] = 3。（目标是凑齐target=4）
 那么就是先把1加⼊计算，然后再把3加⼊计算，得到的⽅法数量只有{1, 3}这种情况。⽽不会出现{3, 1}的情况。
 for循环时虽然都会出现以下情况，让你误以为{1, 3} 和 {3, 1}都算进去了。你从头到尾推一遍。其实你会发现，下面1中的dp[3]再凑一个1就可以凑成4（但是这个3是由3个1凑来的），而下面2中的dp[1]再凑一个3就能凑成4（但是这个3就是一个3，而不是3个1凑成的）。所以只会考虑1，3这种情况（因为物品遍历放在外层，3只能出现在1后面！）：

1.   dp[4] += dp[4-1] 即dp[4] += dp[3]
2.   dp[4] += dp[4-3] 即dp[4] += dp[1]

• 1
• 2

 自己手算一遍就知道了，类似的道理for循环颠倒就是排列了。

 而如果先遍历背包再遍历物品，就是排列问题：

for j in range(0, bag_weight+1):
	for i in range(0, len(weight)):
		if j >= weight[i]: 
			dp[j] += dp[j-weight[i]]

• 1
• 2
• 3
• 4

 背包容量的每⼀个值，都是经过 1 和 3的计算，包含了{1, 3} 和 {3, 1}两种情况。

 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
 如果求排列数就是外层for遍历背包，内层for循环遍历物品。

 

????八、完全背包排列问题：

 也就是调换下for循环的位置即可，上面完全背包组合问题中已经作过解释了：

def bag_full_permutation():
    weight = [1, 5]
    bag_weight = 6

    # dp[j]表示装满容量为j的背包一共有dp[j]种组合方法
    dp = [0]*(bag_weight+1)

    # 即背包容量为0，有1种方法即装0件。不能初始化为0毕竟从状态转移公式可见，
    # dp[j]都是依赖j以前的索引的dp值来更新的，若dp[0]=0。那整个dp数组都为0了。
    dp[0] = 1

    # 外循环遍历背包
    for j in range(0, bag_weight + 1):

        # 内循环遍历物品种类
        for i in range(0, len(weight)):
            if j >= weight[i]:
                #在i-1状态时，dp[j]表示从前i-1 种 物品中选取物品装满背包容量为j的组合数。当然我加上物品i后的组合数是不变的
                #dp[j-weight[i]]表示在背包容量为j-weight[i]时，从前i种物品中选取物品装满容量为j的背包的组合数。
                #所以将上面两个加起来就是下式，表示：在背包容量为j时的组合数等于，前i-1 种 物品的组合数（背包容量为j）加上从前 i 种物品中选取物品的组合数(背包容量为j-weight[i])
                dp[j] += dp[j-weight[i]]
    return dp[bag_weight]

print(bag_full_permutation())

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24

 
 

⭐本篇是背包问题的Python实现，关于java实现请看这：
【1】DP经典回顾：背包问题

⭐一些参考链接：
 这篇会讲解一些背包问题的变种题目及常用模板：
【1】一篇文章吃透背包问题！（细致引入+解题模板+例题分析+代码呈现）
 这篇及其系列的DP文章讲解的原理比较全面不错：
【2】动态规划：关于01背包问题，你该了解这些！