A38937. 编程实现现有一个容器，其容量为v（0<v<1001，正整数），同时有n个物品（0<n<=30），每个物品体积大小不同（正整数）。在n个物品中，任取若干个装入容器内，使容器的剩余空间为最小。输入描述输入容器大小V（0<V<1001，正整数）输入物品数量n（0<n<=30）输入n个物品的不同大小（正整数）输出描述剩余最小空间值样例输入100450204519说明：“100”输入的是容器大小V；“4”…
填空题
困难
知识点
题目描述
编程实现
现有一个容器，其容量为v（0<v<1001，正整数），同时有n个物品（0<n<=30），每个物品体积大小不同（正整数）。
在n个物品中，任取若干个装入容器内，使容器的剩余空间为最小。
输入描述
输入容器大小V（0<V<1001，正整数）输入物品数量n（0<n<=30）输入n个物品的不同大小（正整数）
输出描述
剩余最小空间值
样例输入
100
4
50
20
45
19
说明：“100”输入的是容器大小V；“4”输入的是物品数量n；“50"“20"“45，“19”输入的是4个物品体积。
样例输出
5
说明：“5”是容器大小减掉4个物体不同组合后与容器大小最为接近的一组值。（物品组合个数不限制，只找最接近容器大小的值）
参考答案
def fill(lst,room):
if not lst: #物品取完
return room
if not room: #没有空间
return 0
result = fill(lst[1:],room) #空间不够放
if room>=lst[0]: #空间够放
take=fill(lst[1:],room-lst[0])
result=min(take,result)
return result
v=int(input())
n=int(input())
lst=[]
for i in range(n):
lst.append(int(input()))
print(fill(lst,v))
上一题
下一题