目录

一、如此编码

题目背景：

样例输入

样例输出

思路：

代码：

二、何以包邮？

题目背景：

样例输入

样例输出

​编辑思路：

代码：

后续：

总结

一、如此编码

题目背景：

某次测验后，顿顿老师在黑板上留下了一串数字 23333 便飘然而去。凝望着这个神秘数字，小 P 同学不禁陷入了沉思……

样例输入

15 32767
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

样例输出

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

思路：

代码：

n,m=map(int,input().split())
# 由于ai是从下标为1开始的，故给a[0]设置为0
a_=[0]
#输入a[i]
for i in input().split():a_.append(int(i))c_=[1]
#qian_zhui表示前i个a[i]乘积
qian_zhui=1
for i in range(1,n+1):qian_zhui=qian_zhui*a_[i]c_.append(qian_zhui)
# print(c_)
#一行公式搞定bi=(m%c_[i+1]-m%c_[i])/c_[i]
for i in range(n):print(int((m%c_[i+1]-m%c_[i])/c_[i]),end=' ')

二、何以包邮？

题目背景：

新学期伊始，适逢顿顿书城有购书满 x 元包邮的活动，小 P 同学欣然前往准备买些参考书。
一番浏览后，小 P 初步筛选出 n 本书加入购物车中，其中第 i 本（1≤i≤n）的价格为 ai 元。
考虑到预算有限，在最终付款前小 P 决定再从购物车中删去几本书（也可以不删），使得剩余图书的价格总和 m 在满足包邮条件（m≥x）的前提下最小。

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

样例输入

4 100
20
90
60
60

样例输出

110

思路：

暴力枚举肯定超时，它在提示中也说了。

所以得换个思路，其实这题可以看作背包问题，背包问题请参考：

python 01背包问题https://blog.csdn.net/Renascence_6/article/details/115698776 01 背包问题描述：

在本题中，我们可以把N件物品 看成书的数量即n，容量V则等价于满足包邮的条件x，第i件物品的体积和价值都看作 书的价格a_i。

但是我们所选书的总价值得大于或等于包邮条件x，故：

（1）总价值等于包邮条件x，输出res

（2）总价值小于包邮条件x，说明当前所选书价值之和，再加上任意一本书籍的价值将超过包邮条件，故我们只要在所剩书籍中选择最小价值的书籍，就能包邮且花费最小

代码：

代码如下：

n,x=map(int,input().split())
books=[int(input()) for i in range(n)]
num=10*6+1
v=[0]*num
w=[0]*num
f=[[0]*num for i in range(num)]
#第i件物品的体积和价值都看作 书的价格a_i。
for i in range(1,n+1):v[i]=books[i-1]w[i]=books[i-1]
#01背包问题模板
# ------------------------
for i in range(1,n+1):for j in range(x+1):f[i][j]=f[i-1][j]if j>=v[i]:f[i][j] = max(f[i][j], f[i - 1][j - v[i]]+w[i])
res=0
for i in range(x+1):res=max(res,f[n][i])
# -------------------------
b=x
result=books
#去除掉已选书籍
for i in range(n,0,-1):if f[i][b]>f[i-1][b]:result.remove(v[i])b-=w[i]
#判断
if res<x:print(min(result)+res)
else:print(res)

后续：

总结