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)
相关推荐
投递深圳同为数码等公司10个岗位 点赞 评论 收藏
分享
06-02 19:23
华南理工大学 Java 
屌丝逆袭咸鱼计划：心态摆好，man，晚点找早点找到最后都是为了提升自己好进正职，努力提升自己才是最关键的😤难道说现在找不到找的太晚了就炸了可以鸡鸡了吗😤早实习晚实习不都是为了以后多积累，大四学长有的秋招进的也不妨碍有的春招进，人生就这样 点赞 评论 收藏
分享
07-25 11:26
清华大学 Java 
段哥亡命职场：不得不说，我是理解你的，你能发出来足见你是个坦诚的人，至少敢于直面自己的内心和过往的过错。
这个世界没有想象中那样非黑即白，无论是农村还是城市，在看不见的阴影里，多的是这样的事。
更多的人选择站在制高点去谩骂，一方面是社会的道德是需要制高点的，另一方面，很多人不经他人苦，却劝他人善。
大部分的我们，连自己生命的意义尚且不能明晰，道德、法律、困境，众多因果交织，人会迷失在其中，只有真的走出来之后才能看明白，可是没走出来的时候呢？谁又能保证自己能走的好，走的对呢？
可是这种问题有些人是遇不到的，不去追寻，不去探寻，也就没了这些烦恼，我总说人生的意义在过程里，没了目标也就没了过程。
限于篇幅，没法完全言明，总之，这世界是个巨大的草台班子，没什么过不去了，勇敢面对，革故鼎新才是正确，祝你早日走出来。
查看图片 点赞 评论 收藏
分享