想查看其他题的真题及题解的同学可以前往查看：CCF-CSP真题附题解大全
| 试题编号： | 202209-2 |
| 试题名称： | 何以包邮？ |
| 时间限制： | 1.0s |
| 内存限制： | 512.0MB |
| 问题描述： |
题目描述新学期伊始，适逢顿顿书城有购书满 x 元包邮的活动，小 P 同学欣然前往准备买些参考书。 试帮助小 P 计算，最终选购哪些书可以在凑够 x 元包邮的前提下花费最小？ 输入格式从标准输入读入数据。 输入的第一行包含空格分隔的两个正整数 n 和 x，分别表示购物车中图书数量和包邮条件。 接下来输入 n 行，其中第 i 行（1≤i≤n）仅包含一个正整数 ai，表示购物车中第 i 本书的价格。输入数据保证 n 本书的价格总和不小于 x。 输出格式输出到标准输出。 仅输出一个正整数，表示在满足包邮条件下的最小花费。 样例1输入
样例1输出
样例1解释
样例2输入
样例2输出
样例2解释
样例3输入
样例3输出
样例3解释
子任务70% 的测试数据满足：n≤15； 全部的测试数据满足：n≤30，每本书的价格 ai≤104 且 x≤a1+a2+⋯+an。 提示对于 70% 的测试数据，直接枚举所有可能的情况即可。 |
真题来源：何以包邮？
感兴趣的同学可以如此编码进去进行练习提交
直接无脑解(70分)：
# 输入购物车中的图书数量n和包邮最低值x
n, x = map(int,input().split())
# 设置a来存储每个数的价格
a = []
# 设置最低消费的价格
min_money = n*x
# 存储各种搭配的价格
cost = []
# 进行遍历，将每本书的价格依次存入a
for i in range(n):
t = int(input())
a.append(t)
# 对所有书本的价格进行从低到高的排序
a.sort()
# 开始遍历
for i in a:
# 设置集合存储可能出现搭配的价格
temp = set()
if not cost:
cost.append(i)
continue
for j in cost:
# 判断是否小于最小的包邮值
c = i+j
if c<x:
temp.add(c)
continue
else:
min_money = min(min_money,c)
break
for k in temp:
cost.append(k)
cost.sort()
print(min_money)运行结果：
错误解析：
这种解法属于第二题看到题直白写就好，这个题解虽然有70分，但是我在写的时候没有把每一本书做标记，所以有些书可能重复购买了两次，这是不符题意的，但也有70分入手。
满分题解：
# 输入购物车中的图书数量n和包邮最低值x
n, x = map(int,input().split())
# 设置a来存储每个数的价格
a = []
# 设置动态规划数组存储每个价格的最小花费
dp = [0]*(n*x)
# 进行遍历，将每本书的价格依次存入a
for i in range(n):
t = int(input())
a.append(t)
# 设置pre来保存目前满足包邮的最小花费
pre = sum(a)
# 01背包解法，将每个地方的最优解存入dp数组中
for i in range(n):
for j in range(pre,a[i]-1,-1):
dp[j] = max(dp[j],dp[j-a[i]]+a[i])
# 从x开始遍历，找到超过x的dp[i]
for i in range(x,pre+1):
if dp[i]>=x:
print(dp[i])
break运行结果：
题解解析：
我在里面用了类似01背包动态规划得到概念去解的，我本来以为这种可能会出现超时现象，试了一下发现是可以成功，就用这个解了。
文章出处登录后可见！
