2023-09-02 19:14 The University of New South Wales 算法工程师
关注
今年某公司的动态规划的题，我的问题在哪儿
n,m,x分别是有n种商品，m张优惠券，每张优惠券可以抵扣x元，同一个商品可以用多张优惠券，但不能小于0元，也就是
max(cost - k * x, 0))
要求在有m张券的时候，买所有物品花最少的钱是多少？
n,m,x = [5, 4, 5]
costs = [5, 9, 3, 3, 7]
给的例子是这个，答案是8，分别在1,2,5用1,2,1张券
我的问题是，我跑我的dp，例子是能对的，但跑测试，会超内存，题里面的我记得n,m,x都可以是很大的范围。
我想问，我是因为dp的思路不对呢？还是有什么方法能解决超内存的问题？我有试过用字典储存，但又会超时间，已经遇上这种问题第二次了，想找大佬咨询一下！谢谢！
max(cost - k * x, 0))
要求在有m张券的时候，买所有物品花最少的钱是多少？
n,m,x = [5, 4, 5]
costs = [5, 9, 3, 3, 7]
给的例子是这个，答案是8，分别在1,2,5用1,2,1张券
我的问题是，我跑我的dp，例子是能对的，但跑测试，会超内存，题里面的我记得n,m,x都可以是很大的范围。
我想问，我是因为dp的思路不对呢？还是有什么方法能解决超内存的问题？我有试过用字典储存，但又会超时间，已经遇上这种问题第二次了，想找大佬咨询一下！谢谢！
全部评论
爱吃香菜的杰克在创作
University College London 自然语言处理
时间复杂度nlogn，空间复杂度n
def minimum_cost_to_buy_all_goods(n, m, x, costs):
costs.sort(reverse=True)
for i in range(len(costs)):
number=costs[i]//x
if number==0:
pass
elif m>number:
costs[i]-=number*x
m-=number
else:
costs[i]-=m*x
m=0
costs.sort(reverse=True)
for i in range(m):
costs[i]=0
return sum(costs)
# Example
n, m, x = [5, 4, 5]
costs = [5, 9, 3, 3, 7]
minimum_cost_to_buy_all_goods(n, m, x, costs)
相关推荐
小鹏汽车开奖8人在聊 06-30 15:54
湖北文理学院 Java 
点赞 评论 收藏
分享
07-08 16:21
四川农业大学 招聘专员 点赞 评论 收藏
分享
查看22道真题和解析