05. 背包问题知识(五)
05. 背包问题知识(五)
8. 背包问题变种
8.1 求恰好装满背包的最大价值
背包问题求恰好装满背包的最大价值:在给定背包重量
,每件物品重量 ,物品间相互关系(分组、依赖等)的背包问题中,请问在恰好装满背包的情况下,能装入背包的最大价值总和是多少?
在背包问题中,有的题目不要求把背包装满,而有的题目要求恰好装满背包。
如果题目要求「恰好装满背包」,则我们可在原有状态定义、状态转移方程的基础上,在初始化时,令
这是因为:初始化的
如果不要求恰好装满背包,那么:
- 任何载重上限下的背包,在不放入任何物品时,都有一个合法解,此时背包所含物品的最大价值为
,即 。
而如果要求恰好装满背包,那么:
- 只有载重上限为
的背包,在不放入物品时,能够恰好装满背包(有合法解),此时背包所含物品的最大价值为 ,即 。 - 其他载重上限下的背包,在放入物品的时,都不能恰好装满背包(都没有合法解),此时背包所含物品的最大价值属于未定义状态,值应为
,即 。
这样在进行状态转移时,我们可以通过判断
下面我们以「0-1 背包问题」求恰好装满背包的最大价值为例。
0-1 背包问题求恰好装满背包的最大价值:有
种物品和一个最多能装重量为 的背包,第 种物品的重量为 ,价值为 ,每件物品有且只有 件。请问在恰好装满背包的情况下,能装入背包的最大价值总和是多少?
思路 1:动态规划 + 一维状态
- 划分阶段:按照当前背包的载重上限进行阶段划分。
- 定义状态:定义状态
表示为:将物品装入一个最多能装重量为 的背包中,恰好装满背包的情况下,能装入背包的最大价值总和。 - 状态转移方程:
- 初始条件:
- 只有载重上限为
的背包,在不放入物品时,能够恰好装满背包(有合法解),此时背包所含物品的最大价值为 ,即 。 - 其他载重上限下的背包,在放入物品的时,都不能恰好装满背包(都没有合法解),此时背包所含物品的最大价值属于未定义状态,值应为
,即 。
- 只有载重上限为
- 最终结果:根据我们之前定义的状态,
表示为:将物品装入最多能装重量为 的背包中的方案总数。则最终结果为 ,其中 为背包的载重上限。
思路 1:代码
class Solution:
# 0-1 背包问题 求恰好装满背包的最大价值
def zeroOnePackJustFillUp(self, weight: [int], value: [int], W: int):
size = len(weight)
dp = [float('-inf') for _ in range(W + 1)]
dp[0] = 0
# 枚举前 i 种物品
for i in range(1, size + 1):
# 逆序枚举背包装载重量(避免状态值错误)
for w in range(W, weight[i - 1] - 1, -1):
# dp[w] 取「前 i - 1 件物品装入载重为 w 的背包中的最大价值」与「前 i - 1 件物品装入载重为 w - weight[i - 1] 的背包中,再装入第 i - 1 物品所得的最大价值」两者中的最大值
dp[w] = max(dp[w], dp[w - weight[i - 1]] + value[i - 1])
if dp[W] == float('-inf'):
return -1
return dp[W]
思路 1:算法复杂度
- 时间复杂度:
,其中 为物品种类数量, 为背包的载重上限。 - 空间复杂度:
。
8.2 求方案总数
背包问题求方案数:在给定背包重量
,每件物品重量 ,物品间相互关系(分组、依赖等)的背包问题中,请问在总重量不超过背包载重上限的情况下,或者在总重量不超过某一指定重量的情况下,一共有多少种方案?
这种问题就是将原有状态转移方程中的「求最大值」变为「求和」即可。
下面我们以「0-1 背包问题」求方案总数为例。
0-1 背包问题求方案数:有
件物品和有一个最多能装重量为 的背包。第 件物品的重量为 ,价值为 ,每件物品有且只有 件。 请问在总重量不超过背包载重上限的情况下,一共有多少种方案?
- 如果使用二维状态定义,可定义状态
为:前 件物品放入一个最多能装重量为 的背包中的方案总数。则状态转移方程为: 。 - 如果使用一维状态定义,可定义状态
表示为:将物品装入一个最多能装重量为 的背包中的方案总数。则状态转移方程为: 。
下面我们使用一维状态定义方式解决「0-1 背包问题求解方案数」问题。
思路 2:动态规划 + 一维状态
- 划分阶段:按照物品种类的序号、当前背包的载重上限进行阶段划分。
- 定义状态:定义状态
表示为:将物品装入一个最多能装重量为 的背包中的方案总数。 - 状态转移方程:
- 初始条件:如果背包载重上限为
,则一共有 种方案(什么也不装),即 。 - 最终结果:根据我们之前定义的状态,
表示为:将物品装入最多能装重量为 的背包中的方案总数。则最终结果为 ,其中 为背包的载重上限。
思路 2:代码
class Solution:
# 0-1 背包问题求方案总数
def zeroOnePackNumbers(self, weight: [int], value: [int], W: int):
size = len(weight)
dp = [0 for _ in range(W + 1)]
dp[0] = 1
# 枚举前 i 种物品
for i in range(1, size + 1):
# 逆序枚举背包装载重量
for w in range(W, weight[i - 1] - 1, -1):
# dp[w] = 前 i - 1 件物品装入载重为 w 的背包中的方案数 + 前 i 件物品装入载重为 w - weight[i - 1] 的背包中,再装入第 i - 1 件物品的方案数
dp[w] = dp[w] + dp[w - weight[i - 1]]
return dp[W]
思路 2:复杂度分析
- 时间复杂度:
,其中 为物品种类数量, 为背包的载重上限。 - 空间复杂度:
。
8.3 求最优方案数
背包问题求最优方案数:在给定背包重量
,每件物品重量 、物品价值 ,物品间相互关系(分组、依赖等)的背包问题中,请问在总重量不超过背包载重上限的情况下,使背包总价值最大的方案数是多少?
通过结合「求背包最大可得价值」和「求方案数」两个问题的思路,我们可以分别定义两个状态:
- 定义
表示为:前 种物品放入一个最多能装重量为 的背包中,可获得的最大价值。 - 定义
表示为:前 种物品放入一个最多能装重量为 的背包中,使背包总价值最大的方案数。
下面我们以「0-1 背包问题」求最优方案数为例。
0-1 背包问题求最优方案数:有
种物品和一个最多能装重量为 的背包,第 种物品的重量为 ,价值为 ,每件物品有且只有 件。请问在总重量不超过背包载重上限的情况下,使背包总价值最大的方案数是多少?
思路 3:动态规划
- 划分阶段:按照物品种类的序号、当前背包的载重上限进行阶段划分。
- 定义状态:
- 定义
表示为:前 种物品放入一个最多能装重量为 的背包中,可获得的最大价值。 - 定义
表示为:前 种物品放入一个最多能装重量为 的背包中,使背包总价值最大的方案数。
- 定义
- 状态转移方程:
- 如果
,则说明选择第 件物品获得价值更高,此时方案数 是在 基础上添加了第 件物品,因此方案数不变,即: 。 - 如果
,则说明选择与不选择第 件物品获得价格相等,此时方案数应为两者之和,即: 。 - 如果
,则说明不选择第 件物品获得价值更高,此时方案数等于之前方案数,即: 。
- 如果
- 初始条件:如果背包载重上限为
,则一共有 种方案(什么也不装),即 。 - 最终结果:根据我们之前定义的状态,
表示为:前 种物品放入一个最多能装重量为 的背包中,使背包总价值最大的方案数。则最终结果为 ,其中 为物品的种类数, 为背包的载重上限。
思路 3:代码
class Solution:
# 0-1 背包问题求最优方案数 思路 1
def zeroOnePackMaxProfitNumbers1(self, weight: [int], value: [int], W: int):
size = len(weight)
dp = [[0 for _ in range(W + 1)] for _ in range(size + 1)]
op = [[1 for _ in range(W + 1)] for _ in range(size + 1)]
# 枚举前 i 种物品
for i in range(1, size + 1):
# 枚举背包装载重量
for w in range(W + 1):
# 第 i - 1 件物品装不下
if w < weight[i - 1]:
# dp[i][w] 取「前 i - 1 种物品装入载重为 w 的背包中的最大价值」
dp[i][w] = dp[i - 1][w]
op[i][w] = op[i - 1][w]
else:
# 选择第 i - 1 件物品获得价值更高
if dp[i - 1][w] < dp[i - 1][w - weight[i - 1]] + value[i - 1]:
dp[i][w] = dp[i - 1][w - weight[i - 1]] + value[i - 1]
# 在之前方案基础上添加了第 i - 1 件物品,因此方案数量不变
op[i][w] = op[i - 1][w - weight[i - 1]]
# 两种方式获得价格相等
elif dp[i - 1][w] == dp[i - 1][w - weight[i - 1]] + value[i - 1]:
dp[i][w] = dp[i - 1][w]
# 方案数 = 不使用第 i - 1 件物品的方案数 + 使用第 i - 1 件物品的方案数
op[i][w] = op[i - 1][w] + op[i - 1][w - weight[i - 1]]
# 不选择第 i - 1 件物品获得价值最高
else:
dp[i][w] = dp[i - 1][w]
# 不选择第 i - 1 件物品,与之前方案数相等
op[i][w] = op[i - 1][w]
return op[size][W]
思路 3:复杂度分析
- 时间复杂度:
,其中 为物品种类数量, 为背包的载重上限。 - 空间复杂度:
。
8.4 求具体方案
背包问题求具体方案:在给定背包重量
,每件物品重量 、物品价值 ,物品间相互关系(分组、依赖等)的背包问题中,请问将哪些物品装入背包,可使这些物品的总重量不超过背包载重上限,且价值总和最大?
一般背包问题都是求解一个最优值,但是如果要输出该最优值的具体方案,除了
下面我们以「0-1 背包问题」求具体方案为例。
0-1 背包问题求具体方案:有
种物品和一个最多能装重量为 的背包,第 种物品的重量为 ,价值为 ,每件物品有且只有 件。请问将哪些物品装入背包,可使这些物品的总重量不超过背包载重上限,且价值总和最大?
思路 4:动态规划 + 路径记录
0-1 背包问题的状态转移方程为:
则我们可以再定义一个
- 如果
,说明:转移到 时,选择了前一项 ,并且具体方案中不包括第 件物品。 - 如果
,说明:转移到 时,选择了后一项 ,并且具体方案中包括第 件物品。
思路 4:代码
class Solution:
# 0-1 背包问题求具体方案
def zeroOnePackPrintPath(self, weight: [int], value: [int], W: int):
size = len(weight)
dp = [[0 for _ in range(W + 1)] for _ in range(size + 1)]
path = [[False for _ in range(W + 1)] for _ in range(size + 1)]
# 枚举前 i 种物品
for i in range(1, size + 1):
# 枚举背包装载重量
for w in range(W + 1):
# 第 i - 1 件物品装不下
if w < weight[i - 1]:
# dp[i][w] 取「前 i - 1 种物品装入载重为 w 的背包中的最大价值」
dp[i][w] = dp[i - 1][w]
path[i][w] = False
else:
# 选择第 i - 1 件物品获得价值更高
if dp[i - 1][w] < dp[i - 1][w - weight[i - 1]] + value[i - 1]:
dp[i][w] = dp[i - 1][w - weight[i - 1]] + value[i - 1]
# 取状态转移式第二项:在之前方案基础上添加了第 i - 1 件物品
path[i][w] = True
# 两种方式获得价格相等
elif dp[i - 1][w] == dp[i - 1][w - weight[i - 1]] + value[i - 1]:
dp[i][w] = dp[i - 1][w]
# 取状态转移式第二项:尽量使用第 i - 1 件物品
path[i][w] = True
# 不选择第 i - 1 件物品获得价值最高
else:
dp[i][w] = dp[i - 1][w]
# 取状态转移式第一项:不选择第 i - 1 件物品
path[i][w] = False
res = []
i, w = size, W
while i >= 1 and w >= 0:
if path[i][w]:
res.append(str(i - 1))
w -= weight[i - 1]
i -= 1
return " ".join(res[::-1])
思路 4:复杂度分析
- 时间复杂度:
,其中 为物品种类数量, 为背包的载重上限。 - 空间复杂度:
。
8.5 求字典序最小的具体方案
这里的「字典序最小」指的是序号为
我们仍以「0-1 背包问题」求字典序最小的具体方案为例。
为了使「字典序最小」。我们可以先将物品的序号进行反转,从
这是为了在选择物品时,尽可能的向后选择反转后序号大的物品(即原序号小的物品),从而保证原序号为
思路 5:代码
class Solution:
# 0-1 背包问题求具体方案,要求最小序输出
def zeroOnePackPrintPathMinOrder(self, weight: [int], value: [int], W: int):
size = len(weight)
dp = [[0 for _ in range(W + 1)] for _ in range(size + 1)]
path = [[False for _ in range(W + 1)] for _ in range(size + 1)]
weight.reverse()
value.reverse()
# 枚举前 i 种物品
for i in range(1, size + 1):
# 枚举背包装载重量
for w in range(W + 1):
# 第 i - 1 件物品装不下
if w < weight[i - 1]:
# dp[i][w] 取「前 i - 1 种物品装入载重为 w 的背包中的最大价值」
dp[i][w] = dp[i - 1][w]
path[i][w] = False
else:
# 选择第 i - 1 件物品获得价值更高
if dp[i - 1][w] < dp[i - 1][w - weight[i - 1]] + value[i - 1]:
dp[i][w] = dp[i - 1][w - weight[i - 1]] + value[i - 1]
# 取状态转移式第二项:在之前方案基础上添加了第 i - 1 件物品
path[i][w] = True
# 两种方式获得价格相等
elif dp[i - 1][w] == dp[i - 1][w - weight[i - 1]] + value[i - 1]:
dp[i][w] = dp[i - 1][w]
# 取状态转移式第二项:尽量使用第 i - 1 件物品
path[i][w] = True
# 不选择第 i - 1 件物品获得价值最高
else:
dp[i][w] = dp[i - 1][w]
# 取状态转移式第一项:不选择第 i - 1 件物品
path[i][w] = False
res = []
i, w = size, W
while i >= 1 and w >= 0:
if path[i][w]:
res.append(str(size - i))
w -= weight[i - 1]
i -= 1
return " ".join(res)
思路 5:复杂度分析
- 时间复杂度:
,其中 为物品种类数量, 为背包的载重上限。 - 空间复杂度:
。
参考资料
- 【资料】背包九讲 - 崔添翼
- 【文章】背包 DP - OI Wiki
- 【文章】背包问题——“01背包”最优方案总数分析及实现 - wumuzi 的博客
- 【文章】背包问题——“完全背包”最优方案总数分析及实现 - wumuzi的博客
- 【文章】背包问题——“01背包”及“完全背包”装满背包的方案总数分析及实现 - wumuzi的博客
来源:https://github.com/itcharge/LeetCode-Py