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