CCF 202209-2 何以包邮 python题解(暴力01背包)

题目描述

新学期伊始，适逢顿顿书城有购书满 x元包邮的活动，小 P 同学欣然前往准备买些参考书。

一番浏览后，小 P 初步筛选出 n本书加入购物车中，其中第 i 本（1≤i≤n）的价格为 ai 元。

考虑到预算有限，在最终付款前小 P 决定再从购物车中删去几本书（也可以不删），使得剩余图书的价格总和 m在满足包邮条件（m≥x）的前提下最小。

试帮助小 P 计算，最终选购哪些书可以在凑够 x 元包邮的前提下花费最小？

输入格式

从标准输入读入数据。

输入的第一行包含空格分隔的两个正整数 n和 x，分别表示购物车中图书数量和包邮条件。

接下来输入 n 行，其中第 i 行（1≤i≤n）仅包含一个正整数ai，表示购物车中第 i本书的价格。输入数据保证 n本书的价格总和不小于 x。

输出格式

输出到标准输出。

仅输出一个正整数，表示在满足包邮条件下的最小花费。

样例1输入

4 100
20
90
60
60

Data

样例1输出

110

Data

样例1解释

购买前两本书（20+90）即可包邮且花费最小。

解题思路

解法一：暴力dfs解题（通过70%）

dfs()函数，有两个参数（目前选的书的总价格cost，目前在判断第i本书）

思路：从第一本书开始，枚举每一本书。

例如：df(0,1)：一开始没有已选的书，总书价为0，从第一本书开始判断；此时没有达到dfs()的两个退出条件，因此继续进入下一层dfs()。

# 输入
n, x = map(int, input().split())
A = [0]
for i in range(1, n+1):A.append(int(input()))minCost = 1<<60
# 终止条件，cost < x
def dfs(cost, i):# 达到最低消费，退出if cost >= x:global minCostminCost = min(minCost, cost)return# 超出了图书总本书，退出if i >= n+1:return# 不取这本书，继续搜索dfs(cost, i+1)# 取这本书dfs(cost + A[i], i+1)dfs(0, 1)
print(minCost)

解法二：01背包解题（通过100%）

将选书装入书包的问题，转化为：从书包中拿出书装入另一个袋子的问题。

另一个袋子，总容量为全部书的价格sum减去书包包邮的价格x，在这个袋子不超过sum-x价值的时候，原书包的书都是可以包邮的。

因此，背包问题的最大体积，在这里可以理解为sum-x；背包问题期待的最大价值，在这里对应是袋子里书的总价的最大值。

第一步：计算所有书的总价值

第二步：建一个一维数组dp[]存计算过程中的状态，此处背包问题的背包是袋子，最大“体积”为sum-x

第三步：遍历每一本书，从右往左遍历每一个背包状态，更新每个背包状态的最大值（经典01背包问题）

# 输入：图书总数n， 包邮最低价格x
n, x = map(int, input().split())# 书的价格A
A = [0]
for i in range(n):A.append(int(input()))# 书总价sum,转化为体积sum-x下，书的总value最大
sum = 0
for i in A:sum += i# dp[]存剩余体积下的最大价值
dp = [0 for i in range(sum-x+1)]# 遍历每一本书
for i in range(1, n+1):# 遍历每一个剩余体积（剩下来的金额）for j in range(sum-x, A[i]-1, -1):dp[j] = max(dp[j], (dp[j-A[i]] + A[i]))print(sum-(dp[-1]))    # 袋子的最大价值，即书包的最小价值

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！