背包问题，易如反掌！

大家好，我是吴师兄。

今天群里有同学 cue 我，那我们今天来学习几道有点难度的 背包问题 。

同时也可以刻意的去思考一下如下几个问题：

1. 01背包和完全背包的区别？为什么在内循环过程中，存在逆序遍历和顺序遍历的区别？
2. 路径无关与路径依赖的区别？为什么路径是否依赖，影响了遍历背包/遍历物品的循环顺序？
3. 使用二维dp数组、一维dp数组、一维dp哈希表（或哈希集合）来完成背包问题，它们的区别和联系是什么？
4. 背包问题的dp解法和回溯解法的区别和联系？

能想清楚这些问题的答案，那么无论是动态规划还是背包问题对于你来说都易如反掌！

题目一、充电设备

题目描述

某个充电站，可提供 n 个充电设备，每个充电设备均有对应的输出功率。

任意个充电设备组合的输出功率总和，均构成功率集合 P 的一个元素。

功率集合 P 的最优元素，表示最接近充电站最大输出功率 p_max 的元素。

解题思路

本题的核心问题是如何从 n 个充电设备中选择若干个设备，使其总输出功率尽可能接近但不超过充电站的最大输出功率 p_max 。

这类问题属于 路径无关、判断是否能够取到某值的01背包问题 ，这里的背包容量即为 p_max ，每个设备的输出功率即为物品的重量。

给定 n 个充电设备，每个设备有一个对应的输出功率。我们需要从这些设备中选择若干个，使其总输出功率尽可能接近但不超过最大充电功率 p_max 。下面我们通过代码逐步分析解决方案：

# 输入充电设备数量
n = int(input())
# 输入n个充电设备的功率
devices = list(map(int, input().split()))
# 输入最大充电功率
p_max = int(input())

首先，我们从输入中获取充电设备的数量 n ，每个设备的功率 devices 以及最大充电功率 p_max 。

# 构建二维dp数组，长度为(n+1)*(p_max+1)，为布尔类型的二维数组
# dp[i][j]的含义为在考虑第i个设备时，功率j是否能够取到
dp = [[False] * (p_max + 1) for _ in range(n + 1)]
# 初始化dp[0][0]为True，表示可以取到
dp[0][0] = True

我们初始化一个二维数组 dp ，其中 dp[i][j] 表示在前 i 个设备中，是否存在某些设备组合，使其总功率恰好为 j 。初始条件是 dp[0][0] = True ，即在没有任何设备的情况下，总功率为 0 是可以实现的。

# 遍历每一种设备的功率p
# 注意为了和二维dp数组的索引一一对应，故i从1开始，取到n结束
for i in range(1, n + 1):
    # i是从1开始计数的，故p应为devices[i - 1]
    p = devices[i - 1]
    # 遍历dp[i-1]数组，所有可以取到的功率总和，用pre_p表示
    for pre_p in range(p_max + 1):
        # 假如某个功率总和pre_p可以取到，则更新到dp[i][pre_p]
        if dp[i - 1][pre_p] == True:
            dp[i][pre_p] = True
            # 假如从某个功率总和pre_p出发，加上当前的设备功率p
            # 能够取得的总设备功率为cur_p
            cur_p = p + pre_p
            # 如果cur_p没有超出最大功率限制
            if cur_p <= p_max:
                # 则cur_p是一个可以取得的方案，将dp[i][cur_p]修改为True
                dp[i][cur_p] = True

我们遍历每个设备，对于每个设备 i ，我们从 dp[i-1] 数组中找到所有可能的功率 pre_p ，并更新当前设备的功率组合到 dp[i] 。如果 pre_p 是可以实现的总功率，则 cur_p = pre_p + p 也是可以实现的总功率（前提是 cur_p <= p_max ）。

# 输出dp[-1]数组中为True的最大值，即为小于等于p_max的最大功率
print(max((i for i in range(p_max + 1) if dp[-1][i])))

最终，我们需要找到 dp[n] 数组中最大且为 True 的值，这个值就是最接近且不超过 p_max 的最大功率。

代码

2维DP数组

# 输入充电设备数量
n = int(input())
# 输入n个充电设备的功率
devices = list(map(int, input().split()))
# 输入最大充电功率
p_max = int(input())


# 构建二维dp数组，长度为(n+1)*(p_max+1)，为布尔类型的二维数组
# dp[i][j]的含义为
# 在考虑第i个设备时，功率j是否能够取到
dp = [[False] * (p_max+1) for _ in range(n+1)]
# 初始化dp[0][0]为True，表示可以取到
dp[0][0] = True

# 遍历每一种设备的功率p
# 注意为了和二维dp数组的索引一一对应，故i从1开始，取到n结束
for i in range(1, n+1):
    # i是从1开始计数的，故p应为devices[i-1]
    p = devices[i-1]
    # 遍历dp[i-1]数组，所有可以取到的功率总和，用pre_p表示
    for pre_p in range(0, p_max+1):
        # 假如某个功率总和pre_p可以取到，则更新到dp[i][pre_p]
        if dp[i-1][pre_p] == True:
            dp[i][pre_p] = True
            # 假如从某个功率总和pre_p出发，加上当前的设备功率p
            # 能够取得的总设备功率为cur_p
            cur_p = p + pre_p
            # 如果cur_0没有超出最大功率限制
            if cur_p <= p_max:
                # 则cur_p是一个可以取得的方案，将dp[i][cur_p]修改为True
                dp[i][cur_p] = True

# 输出dp[-1]数组中为True的最大值，即为小于等于p_max的最大功率
print(max((i for i in range(p_max+1) if dp[-1][i])))

1维DP数组

# 输入充电设备数量
n = int(input())
# 输入n个充电设备的功率
devices = list(map(int, input().split()))
# 输入最大充电功率
p_max = int(input())

# 构建一维dp数组，长度为(p_max+1)，为布尔类型的数组
# dp[i]功率i是否能够取到
dp = [False] * (p_max+1)
# 初始化dp[0]为True，表示可以取到
dp[0] = True

# 遍历每一种设备的功率p
for p in devices:
    # 遍历当前dp数组，所有可以取到的功率总和，用pre_p表示
    # 这里必须使用拷贝，因为在本次遍历中，dp数组会发生改变
    # dp数组正在发生的改变，不能在遍历中被考虑
    #
    # 另一种可行的方法是，逆序遍历dp数组
    # 这样可以保证大功率的修改总是发生在遇到小功率之前
    temp = dp[:]
    for pre_p in range(0, p_max+1):
        # 假如从某个功率总和pre_p出发，加上当前的设备功率p
        # 能够取得的总设备功率为cur_p
        if temp[pre_p] == True:
            cur_p = p + pre_p
            # 如果cur_0没有超出最大功率限制




    

            if cur_p <= p_max:
                # 则cur_p是一个可以取得的方案，将dp[cur_p]修改为True
                dp[cur_p] = True

# 输出dp数组中为True的最大值，即为小于等于p_max的最大功率
print(max((i for i in range(p_max+1) if dp[i] == True)))

1维DP哈希表

# 输入充电设备数量
n = int(input())
# 输入n个充电设备的功率
devices = list(map(int, input().split()))
# 输入最大充电功率
p_max = int(input())


# 构建dp哈希集合，集合中的元素表示能够出现的功率总和
dp = set()
# 初始化dp哈希集合包含0，表示不选择任何设备的方案，此时功率总和为0
dp.add(0)


# 遍历每一种设备的功率p
for p in devices:
    # 遍历当前dp哈希集合中，所有可以取到的功率总和，用pre_p表示
    for pre_p in list(dp):
        # 假如从某个功率总和pre_p出发，加上当前的设备功率p
        # 能够取得的总设备功率为cur_p
        cur_p = p + pre_p
        # 如果cur_0没有超出最大功率限制
        if cur_p <= p_max:
            # 则cur_p是一个可以取得的方案，加入dp哈希集合中
            dp.add(cur_p)


# 输出dp数组中的最大值，即为小于等于p_max的最大功率
print(max(dp))

题目二、工作安排

题目描述

小明每周上班都会拿到自己的工作清单，工作清单内包含 n 项工作，每项工作都有对应的耗时时长(单位h)和报酬，工作的总报酬为所有已完成工作的报酬之和。那么请你帮小明安排一下工作，保证小明在指定的工作时间内工作收入最大化。

解题思路

本题属于 路径无关，求和最大值的01背包问题 ，其中每个工作相当于一个「物品」，其耗时时长相当于「物品的重量」，报酬相当于「物品的价值」，而小明的最大工作时间相当于「背包的容量」。我们的目标是找出一个最佳组合，使得在不超过最大工作时间的前提下，报酬最大。

我们可以使用动态规划来解决这个问题。具体步骤如下：

1. 初始化输入 ：读取最大工作时间 max_time 和工作数量 N ，以及每项工作的耗时时长和报酬。
2. 构建动态规划数组 ：使用一个一维数组 dp ，其中 dp[t] 表示在花费 t 小时工作后，能够获得的最大报酬。初始状态是 dp[0] = 0 ，表示在花费 0 小时的情况下，报酬为 0。
3. 状态转移 ：遍历每一项工作，对于每个工作，更新动态规划数组 dp 。
4. 获取结果 ：最终数组 dp 中的最大值即为在不超过最大工作时间的前提下，能够获得的最大报酬。

代码逻辑如下：

1、 输入和初始化 ：首先，读取最大工作时间 max_time 和工作数量 N ，然后初始化两个列表 times 和 wages 来存储每个工作的耗时时长和对应的报酬。最后，初始化一个一维动态规划数组 dp ，长度为 max_time + 1 ，用来存储每个时间段内能够获得的最大报酬。

2、 动态规划数组的构建 ：

• 对于每一项工作 i ，获取其耗时时长 t 和报酬 w 。
• 为了防止重复计算和保证每项工作只能选择一次，采用逆序遍历当前的 dp 数组。即从 max_time 到 0 逆序遍历。
• 在逆序遍历中，对于每个可能的已用时间 pre_t ，计算加入当前工作的总时间 cur_t = t + pre_t 。如果 cur_t 没有超过 max_time ，则更新 dp[cur_t] 为 max(dp[cur_t], dp[pre_t] + w) 。

3、 输出结果 ：最后，动态规划数组 dp 中的最大值即为在给定最大工作时间内能够获得的最大报酬。

代码

1维DP数组

# 输入最大工作时间max_time和工作数量N
max_time, N = map(int, input().split())

times = list()
wages = list()

# 输入N份工作的时间和报酬
for _ in range(N):
    t, w = map(int, input().split())
    times.append(t)
    wages.append(w)


# 初始化1维dp数组，长度为 max+time + 1
# dp[t] = w 表示用t时间能够获得最多的总报酬w
# dp[0] = 0表示在花费了0的时间只能获得0的报酬
dp = [0] * (max_time+1)

# 遍历每一份工作i
for i in range(N):
    # 分别获得当前工作i的时间t和报酬w
    t = times[i]
    w = wages[i]
    # 01背包，逆序遍历前置时间pre_t
    for pre_t in range(max_time, -1, -1):
        # 获取pre_t对应的最高报酬
        pre_w = dp[pre_t]
        # 假如从某个工作时长pre_t出发，加上当前工作时间t
        # 所需要的总时间用cur_t表示
        cur_t = t+pre_t
        # 如果cur_t没有超出总限制时长
        if cur_t <= max_time:
            # 如果先前用pre_t时间获得的报酬pre_w加上当前工作获得的报酬w
            # 比原先的dp[cur_t]更大（默认为0），则更新dp[cur_t]
            dp[cur_t] = max(dp[cur_t], pre_w + w)


# 输出dp数组中的最大值
print(max(dp))

1维DP哈希表

from collections import defaultdict


# 输入最大工作时间max_time和工作数量N
max_time, N = map(int, input().split())

times = list()
wages = list()

# 输入N份工作的时间和报酬
for _ in range(N):
    t, w = map(int, input().split())
    times.append(t)
    wages.append(w)


# 初始化dp哈希表，key为时间t，value为报酬w
# dp[t] = w 表示用t时间能够获得最多的总报酬w
# dp[0] = 0表示在花费了0的时间只能获得0的报酬
# 注意此处构建 max_time * N 的dp二维数组也是可行的，
# 但由于max_time最大值为10^5，用哈希表更加节省空间
dp = defaultdict(int)
dp[0] = 0


# 遍历每一份工作i
for i in range(N):
    # 分别获得当前工作i的时间t和报酬w
    t = times[i]
    w = wages[i]
    # 遍历当前dp哈希表中，所有的时间和报酬，用pre_t, pre_w表示
    for pre_t, pre_w in list(dp.items()):
        # 假如从某个工作时长pre_t出发，加上当前工作时间t
        # 所需要的总时间用cur_t表示
        cur_t = t+pre_t
        # 如果cur_t没有超出总限制时长
        if cur_t <= max_time:
            # 如果先前用pre_t时间获得的报酬pre_w加上当前工作获得的报酬w
            # 比原先的dp[cur_t]更大（默认为0），则更新dp[cur_t]
            dp[cur_t] = max(dp[cur_t], pre_w + w)


# 输出dp哈希表中的最大值
print(max(dp.values()))

题目三、代表团坐车

题目描述

某组织举行会议，来了多个代表团同时到达，接待处只有一辆汽车，可以同时接待多个代表团，为了提高车辆利用率，请帮接待员计算可以坐满车的接待方案，输出方案数量。

约束：

1. 一个团只能上一辆车，并且代表团人数（代表团数量小于 30 ，每个代表团人数小于 30 ）小于汽车容量（汽车容量小于 100 ）
2. 需要将车辆坐满

解题思路

其中，我们需要找到所有可能的组合，使得总人数恰好等于汽车容量 max_num 。

具体来说，每个代表团的人数相当于背包中的物品重量，我们需要通过选择这些物品来恰好填满背包。

背包问题！

动态规划数组 dp 的定义和状态转移如下：

• 定义 ： dp[i] 表示汽车载重为 i 时，所有可能的乘坐方案数量。
• 初始化 ： dp[0] = 1 ，表示在汽车为空的情况下，只有一种方案（即什么都不做）。
• 状态转移 ：对于每个代表团人数 num ，我们逆序遍历当前的载重 pre_num ，更新 dp[pre_num + num] 的值。逆序遍历是为了防止重复计算。