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)
相关推荐
小舰大杀四方：现在的就业环境真是艰难，你好歹磕磕绊绊也走过三面了，回答的肯定也不错，尤其是hr面问了你这么多问题，，，结果一周都没消息。想知道现在的公司到底在高贵什么啊
点赞 评论 收藏
分享
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
2025-12-09 23:28
32*15+六位数签字费💰。bg985硕，base上海后端。这个价今年在字节这算什么档位呢。美团开了ssp，30k的月base，hr说a不了。字节美团月base加签字费总包加起来差不多。有点纠结选哪个
东东咚昸：看组，节子开六位数签字费你要考虑好入职后的
点赞 评论 收藏
分享
