资源简介

(共22张PPT)
课时41 背包问题
一、背包问题的基本概念
1. 背包问题是一个经典的组合优化问题，核心目标是：在给定背包容量限制下，选择若干物品，使得这些物品的总价值最大。
2. 分类。
（1）0-1 背包问题：每种物品只能选或不选（不可分割）。
（2）完全背包问题：每种物品可以选无限次。
（3）多重背包问题：每种物品有数量限制。
3. 问题输入。
（1）背包容量 w。
（2）物品列表，每个物品包含重量 weight 和价值 value。
4. 问题输出：选择哪些物品，使得总重量不超过 w，且总价值最大。
1. 状态定义：定义二维数组 dp[i][w]，表示前 i 个物品在背包容量为 w 时的最大价值。
2. 状态转移方程。
（1）对于第 i个物品，有两种选择：
①不选：dp[i][w]=dp[i-1][w]。
②选（需满足 weight[i]≤w）：dp[i][w]=dp[i-1][w-weight[i]]+value[i]。
（2）取两者中的最大值：dp[i] [w]=max(dp[i-1][w],dp[i-1][w-weight[i]]+ value[i])。
3. 初始化边界条件：dp[0][w]=0（没有物品时价值为 0）。
二、0-1 背包问题的动态规划解法
4.Python 实现。
def knapsack_01(weight,value,capacity):
n=len(weight)
#数组 dp 中的行表示物品序号，列表示背包容量
dp=[[0]*(capacity+1) for _ in range(n+1)]
for i in range(1,n+1):
for w in range(capacity+1):
'''注意：第 i 个物品的重量和价值存储在列表 weight 和 value 的下标 i-1 处'''
if weight[i-1]>w:
dp[i][w]=dp[i-1][w]
else:
dp[i][w]=max(dp[i-1][w],dp[i-1][wweight[i-1]]+value[i-1])
return dp[n][capacity] #返回最大价值
weight=[1,3,4]
value=[15,20,30]
capacity=5 #背包容量
print(knapsack_01(weight,value,capacity))
#输出：45（选物品 1 和 3）
5.空间优化（滚动数组）：由于dp[i][w]仅依赖上一行dp[i-1][…]，可以将二维数组压缩为一维数组。
def knapsack_01_optimized(weight,value,capacity):
n=len(weight)
dp=[0]*(capacity+1)
for i in range(n):
#逆序遍历避免覆盖
for w in range(capacity,weight[i]-1,-1):
dp[w]=max(dp[w],dp[w-weight[i]]+value[i])
return dp[capacity]
print(knapsack_01_optimized(weight,value,capacity))
1. 状态转移方程：dp[w]=max(dp[w],dp[w-weight[i]]+value[i])。
2.Python 实现。
def complete_knapsack(weight,value,capacity):
n=len(weight)
dp=[0]*(capacity+1)
for i in range(n):
for w in range(weight[i],capacity+1):
dp[w]=max(dp[w],dp[w-weight[i]]+value[i])
return dp[capacity]
weight=[1,3,4]
value=[15,20,30]
capacity=4
print(complete_knapsack(weight,value,capacity))
#输出：60（选 4 次物品 1）
三、完全背包问题的动态规划解法
典例 1 小明即将搬家，他的行李箱最大承重为 10 公斤。有若干物品可供选择，每个物品有重量（公斤）和实用价值（分），小明希望在不超重的前提下，使总实用价值最大。编写程序求解最优组合。请回答下列问题：
（1）若可选物品如表所示，则行李箱能装入的最大总实用价值为　　　　　　　分。
31
（2）实现上述功能的 Python 程序如下，请在画线处填入合适的代码。
def knapsack(weights,values,capacity):
n=len(weights)
dp=[[0]*(capacity+1) for _ in range(n+1)]
for i in range(1,n+1):
for w in range(1,capacity+1):
if weights[i-1]>w:
dp[i][w]=dp[i-1][w]
else:
dp[i][w]=max(　　 ① 　　,
　　 ② 　　)
#回溯找到具体物品组合
selected=[]
w=capacity
dp[i-1][w]
dp[i-1][w-weights[i-1]]+ values[i-1]
for i in range(n,0,-1):
if dp[i][w]!=dp[i-1][w]:
selected.append(i-1)
w-=　　　③　　　1
return dp[n][capacity],selected
weights=[3,4,5,2,1]
values=[8,10,15,5,6]
items=["书","衣服","电脑","零食","相机"]
capacity=10
mv,selected=knapsack(weights,values,capacity)
print("最大总价值：",mv)
print("选择物品：",[items[i] for i in selected])
weights[i-1]
胜券点拨1
明考向 本题主要考查动态规划和背包问题
审关键 在不超重的前提下，使总实用价值最大
考场思维快闪 （1） 最优组合为衣服（4公斤，10分）+电脑（5公斤，15分）+相机（1公斤，6分），总重量为10公斤，总价值为31分
（2） dp[i][w]表示前i个物品在行李箱容量为w时的最大价值。对于第i个物品，若其重量不超过容量w，有两种选择：不选当前物品，则dp[i][w]=dp[i-1][w]。若选择当前物品，则dp[i][w]=dp[i-1][w-weights[i-1]]+values[i-1]，取两者中的最大值。最大价值存储在dp[n][capacity]中，根据动态规划表反推出具体物品组合，若dp[i][w]!=dp[i-1][w]，则表示选择了第i个物品，对应索引为i-1，对应重量为weights[i-1]，将选中物品的索引添加到列表selected中，然后更新剩余物品的重量，即w-=weights[i-1]
典例 2 ［2025 宁波模拟］某网络购物平台流行跨店满减促销活动，如“跨店满 w 元减 m 元”。小明的购物车中有 n 个商品，他的预算不超过 2*w-1 元，因此至少有一个商品的价格低于 2*w 元。为获得最大性价比，小明计划从购物车中挑选若干个商品，在凑够满减条件的前提下，消费总额尽可能小，若存在多个满足条件的商品组合，则优先购买单价最高的商品。
　　算法思路如下：首先，为优先购买单价最高的商品，对购物车中的商品按照价格升序排序。接下来，从第一个商品（i=0）开始，逐渐扩大商品的选择范围，并用二维数组 states 记录在当前可选商品范围内可能出现的消费总额。states[i][j]为 True 表示前 i+1（0~i）个商品存在消费总额恰好为 j 的购买组合。最后，当选择范围扩大到所有商品时，从有可能产生的消费总额中找出最优解。若找不到可行方案，则输出“没有可行方案”。
　　例如，本次跨店满减促销活动为“跨店满 200 元减 50 元”，购物车中商品的价格依次为[56,54,
35,44,55,48]，程序运行界面如图所示。
请回答下列问题：
（1）若购物车中商品的价格依次为[54,50,23,58,
39,55]，则参加“跨店满 200 元减 50 元”后，支付的最小金额是　　　　　　　元。
（2）为优先购买单价最高的商品，小明先对购物车中的商品按价格升序排序。实现该功能的 Python 程序如下，请在画线处填入合适的代码。
def sort(arr):
for i in range(1,len(arr)):
key=arr[i]
　　　　　　　1
while j>=0 and keyarr[j+1]=arr[j]
j=j-1
arr[j+1]=key
return arr
151
j=i-1
（3）实现上述功能的部分 Python 程序如下，请在画线处填入合适的代码。
def solve(items,w):
n=len(items)
'''二维数组 states 记录消费状态，若总额达到 2*w，则超出顾客预算'''
states=[[False]*(2*w) for i in range(n)]
#没有购买任何商品时，总额为 0 元
states[0][0]=True
#购买第一件商品，总额为 items[0]元
states[0][items[0]]=True
for i in range(1,n):
for j in range(2*w):
if states[i-1][j]:
'''不购买第 i+1 个商品，总额仍为 j 元'''
states[i][j]=True
　　　①　　　1
if sum_price<2*w:
#购买第 i+1 个商品
states[i][sum_price]=
True
j=w
while j<2*w and not states[n-1][j]:
j+=1
if j==2*w:
return -1 #没有可行方案
ans=[]
for i in range(n-1,0,-1):
if j-items[i]>0 or states[i-1][j-items[i]]:
ans.append(items[i])
j=　　　②　　　1
if j!=0:
ans.append(items[0])
return ans
'''随机产生 n 个商品价格存储到 items 中，输入 w 和 m 代表“跨店满 w 元减 m 元”，代码略'''
print("各商品价格为：",items)
items=sort(items) #按商品价格升序排序
ans=solve(items,w) #寻找满减的购物方案
if ans==-1:
print("没有可行方案")
else:
print("选中商品的价格为：",ans)
print("参加满减后支付的最少金额为：",sum(ans)-m)
（4）加框处代码有错，应修改为　　　　　　　。
sum_price=j+items[i]　或其他等价答案
j-items[i]
j-items[i]>=0 and states[i-1][j-items[i]]　或其他等价答案
胜券点拨2
明考向 本题主要考查动态规划和背包问题
审关键 最小化总金额、贪心思想
考场思维快闪 （1） 已知商品价格依次为[54,50,23,58,39,55]，其中满足满减条件的最小金额是201，即价格[54,50,58,39]，由于满减条件是“满200元减50元”，因此实际支付金额为201-50=151
（2） sort(arr)函数为插入排序算法，在排序过程中通过比较key与前面的元素，将大于key的元素逐步向后移动，最后把key插入到正确的位置
（3） ①判断是否可以购买第i+1个商品，需要计算购买该商品后的总额，若新的总额sum_price小于2*w，则更新状态数组states[i][sum_price]为True，表示可以组成这个总额，故填入代码为sum_price=j+items[i]。②在for循环中，逐步倒推商品的选择，若添加了商品i到购物清单中，则当前总额变成j，需要回溯找到之前的状态，即j-items[i]，表示在选择商品i之前的状态，通过j-items[i]来找出前一个可能的状态，从而决定是否继续回溯
（4） 在满减购物计划中，必须检查剩余总额非负（j-items[i]>=0）且前i个商品可以组成剩余总额（states[i-1][j-items[i]]），确保在前i个商品中，总额j-items[i]是有效的，并且可以通过已有的商品组合达到该价格
total_w=0 #当前集装箱的总重量
curr_comb=[] #当前组合的集装箱索引
for j in range(n): #遍历每一个物品
#若第 j位为 1，则表示选择了第 j 个物品
if i//2**j%2:
　　　　　　　1
#记录选中的集装箱索引
curr_comb.append(j)
'''如果当前组合的重量不超过轮船载重，则更新最大重量'''
if total_w<=c and total_w>best_weight:
best_weight=total_w
#更新最优集装箱索引组合
best_comb=curr_comb
print(f"最优装载重量：{best_weight}")
print(f"集装箱索引：{best_comb}")
1.有 n 个集装箱要装上一艘载重量为 c 的轮船，其中集装箱 i 的重量为 w[i]。现编写 Python 程序找出一种最优装载方案，将轮船尽可能装满，即在装载体积不受限制的情况下，将尽可能重的集装箱装上轮船。
（1）用二进制枚举法解决装载问题的 Python 程序如下，请在划线处填入合适的代码。
w=[2,3,5,6,6] #集装箱重量列表
n=len(w) #集装箱数量
c=10 #轮船的最大载重量
best_weight=0 #初始化最优装载重量
best_comb=[] #用于最优解的集装箱索引
'''使用二进制法枚举所有物品的组合情况，共 2**n 种组合'''
for i in range(2**n): #表示所有 0、1 组合
total_w+=w[j]
（2）用动态规划解决装载问题的 Python 程序如下，请在划线处填入合适的代码。
w=[2,3,5,6,6] #每个集装箱的重量
n=len(w) #集装箱数量
c=10 #轮船载重量
#二维递推数组
f=[[0]*(c+1) for _ in range(n+1)]
for i in range(n):
for v in range(c+1):
'''轮船载重量 v 大于等于集装箱重量 w[i]时才有可能装'''
if v>=w[i]:
#装 w[i]和不装的较大者
f[i+1][v]=max
(　　　　　　　)
f[i][v-w[i]]+w[i],f[i][v]
else:
f[i+1][v]=f[i][v] #不装
print(f"最大装载重量：{f[n][c]}")
loaded=[] #回溯找出装载的集装箱
v=c
for i in range(n-1,-1,-1):
if f[i+1][v]!=f[i][v]:
loaded.append(i) #记录集装箱编号
v-=w[i]
print("装载的集装箱编号：",loaded[::-1])
（3）动态规划方法中，由于 f[i+1][v]仅依赖上一行 f[i][…]，可以将二维数组压缩为一维数组。实现代码如下，请在划线处填入合适的代码。
w=[2,3,5,6,6] #每个集装箱的重量
n=len(w) #集装箱数量
c=10 #轮船载重量
f=[0]*(c+1)
for i in range(n): #集装箱 i
#装载 w[i]，逆序确保每个集装箱只装载一次
for v in range(c,w[i]-1,-1):
#装 w[i]和不装的较大者
f[v]=max(f[v-w[i]]+w[i],f[v])
f[c]
print(f"最大装载重量：
{　　　　　　　}")
loaded=[] #回溯找出装载的集装箱
v=c
for i in range(n-1,-1,-1):
if f[i+1][v]!=f[i][v]:
#记录集装箱编号
loaded.append(i)
v-=w[i]
print("装载的集装箱编号：",loaded[::
-1])
（1）选择了第 j 个物品，则累加该物品的重量到 total_w，故填入代码为 total_w+=w[j]。 （2）f[i+1] [v]表示前 i+1 个集装箱在载重量不超过 v 的情况下能够装载的最大重量，它等于前 i 个集装箱在载重量不超过 v-w[i]的情况下能够装载的最大重量+w[i]与上一个 f[i] [v]的较大者。 （3）f[v]表示容量为 v 时的最大装载重量，要输出载重量为 c 的最大装载重量，故填入代码为 f[c]。
2.乐乐参加了商场打折活动，商场的每个商品都有一个原价和一个优惠价，乐乐拥有p次机会以优惠价购买商品，他希望在购物总金额不超过m元的前提下尽可能多地购买商品。编写Python程序，计算出应该乐乐购买哪些商品。
　　例如，每个商品的原价和优惠价如图a所示，乐乐有1次用优惠价购买商品的机会，且购买的金额不能超出9元，则乐乐最多购买3个商品，分别是商品0、商品1和商品2，且商品2以优惠价购买，最后剩余金额为1元。
请回答下列问题：
（1）如图a所示的数据，若乐乐有2次用优惠价购买商品的机会，则乐乐购买完所有4件商品，至少需要的购物总金额m是　　　　　　　。
11
（2）定义如下get_sort(data,k)函数，功能是返回data中以k列数据升序排列后的商品编号列表，请在画线处填入合适的代码。
def get_sort(data,k):
n=len(data)
#列表b中保存商品编号0~n-1
b=[i for i in range(n)]
for i in range(n):
for j in range(n-i-1):
if 　　　　　　　:
b[j],b[j+1]=b[j+1],b[j]
return b
data[b[j]][k]>data[b[j+1]][k]
（3）实现上述功能的Python程序如下，程序运行界面如图b所示，请在画线处填入合适的代码。'''读取商品价格，并将其存储在列表data中，data的每个元素包含商品的原价和优惠价两个数据项；商品数量存储在n中，乐乐拥有的现金存储在m中，优惠次数存储在p中；代码略'''
#获取以商品原价升序排列后的商品编号
org=get_sort(data,0)
#获取以商品优惠价升序排列后的商品编号
pre=get_sort(data,1)
'''r[i]保存某次购买的折扣（商品原价-优惠价），且r[0]r=[0]*p
#f[i]=True表示i号商品已经被购买
f=[False]*n;ans=[]
i=j=cnt=0
while 　　　①　　　:
while(f[org[i]]):
i+=1
while(f[pre[j]]):
j+=1
#若用优惠价购买商品更划算
if 　　　②　　　:
d=pre[j]
cost=data[d][1]+r[0]
r[0]=data[d][0]-data[d][1]
k=0
while kr[k+1]:
r[k],r[k+1]=r[k+1],r[k]
k+=1
else:
d=org[i];cost=data[d][0]
if mbreak
m-=cost
　　　③　　　1
ans.append(d);cnt+=1
print("购买商品数量：",cnt)
print("购买商品编号：",ans)
print("剩余金额：",m)
cnt0
data[org[i]][0]>data[pre[j]][1]+r[0]
f[d]=True
（1）若要购买所有商品，则用优惠价购买原价与优惠价差值最大的2个商品，即商品2、3，购物总金额为3+2+3+3=11。　（2）若data中前一个元素的k列数据大于后一个元素的k列数据，则交换对应的商品编号，故填入代码为data[b[j]][k]>data[b[j+1]][k]。　（3）①cnt表示购买商品的数量，能够购买商品的条件是未买完所有商品（cnt0），故填入代码为cnt0。②org[i]指向当前未购买商品中原价最小的商品，pre[j]指向当前未购买商品中优惠价最小的商品，当选择优惠价购买时，需确保“原价>优惠价+当前最小折扣调整值”（r[0]是已用折扣中的最小值），故填入代码为data[org[i]][0]>data[pre[j]][1]+r[0]。③列表f标记商品是否被购买，其初始值为False，d为当前购买的商品编号，故填入代码为f[d]=True。

展开更多......

收起↑