头条面试遇到的算法题

满减凑单问题

假设双十一购物，有满xx减xx的活动（例如满100-30），我现在购物车中有充足的商品，商品价格各不相同，请帮我利用购物车内商品凑单，每个商品只能用一次，使我获得最大优惠（即凑单商品总价大于等于100但最近接近100）

输入：商品价格数组，凑单金额

输出：总价超过凑单金额但最接近的金额

例如

输入 [90, 52, 30, 65, 20] 100

输出 102

求大佬指导

#字节跳动##笔试题目#
全部评论
我理解这应该是背包问题，容量设置为所有商品的单价和，计算完dp数组，从容量为100开始往后遍历，找到第一个花费大于等于100的就是最终结果
2 回复
分享
发布于 2020-04-16 06:59
小根堆？
点赞 回复
分享
发布于 2020-04-16 00:42
小红书
校招火热招聘中
官网直投
dp吧，感觉01背包
点赞 回复
分享
发布于 2020-04-16 07:27
背包问题。
点赞 回复
分享
发布于 2020-04-16 07:53
好像还有一个条件，这些卷存在互斥，或者只能用在特定的商品上，这类问题怎么解决
点赞 回复
分享
发布于 2020-04-16 10:17
如果商品可以用多次但是有个数限制。时间复杂度不能改变。怎么做。
点赞 回复
分享
发布于 2020-04-16 20:24
楼主，只要一天没走完所有面试就是凉了吗？二面完让我等通知
点赞 回复
分享
发布于 2020-04-22 16:20
01背包问题变种：建立一个备忘录二维表(列是100*n)，表初始化后，从100列开始忘后找。
点赞 回复
分享
发布于 2021-01-08 11:09

相关推荐

头像
X爱上班
04-19 17:57
帆软软件_前端开发工程师
帆软春招补录，急招！5.15网申截止
【❗❗重要】帆软春招网申截止时间：5.15 校招逐渐接近尾声，帆软春招补录开始啦~  👉部分校招重点岗位新增HC：研发、产品、设计、销售！且补录岗位hc余量较多，还没有投递的同学们抓紧了 👉除补录岗位外，其余岗位也在招聘中，具体可见招聘官网 👉目前在大厂流程的同学，可以投递找个保底，我司也是很不错的。没投递的同学抓紧时间投递，珍惜最后的机会~ 祝同学们好运常在~🍀🍀🍀 投递链接：https://join.fanruan.com/ 内推码：Er59i1g （使用内推码优先筛选，后台可跟踪简历处理进度 ）     
投递帆软软件等公司8个岗位 >
点赞 评论 收藏
转发
头像
突尼斯海怪0
04-19 14:44
已编辑
上海理工大学 计算机类
还得是大公司啊，见世面了
真的见世面了。。太太太太太太太太幸运了，真的收获满满，开心到飞起，赶紧发帖留念！再次感慨找工作真的要找大公司，资源都是顶配，你能接触到的项目级别、人脉级别、技术栈都是小公司无法比的。我是今年报名参加了欧莱雅BRANDSTORM大赛，遗憾的是没有进全国总决赛，但是好处是被抽中邀请来观赛总决赛了，我想的是长长见识，而且名额机会都非常宝贵，加上我又刚好在上海，没有不来的道理！！！欧莱雅BRANDSTORM大家应该都知道了，前段时间牛客上各种美发黑科技的话题讨论，就是今年的赛题，看科技怎么赋能美发黑科技，我看现场介绍好像是有7500多个队伍参赛，现在是全国18强进入全国总决赛，选出中国冠亚，到时候可以...
点赞 评论 收藏
转发
头像
Lindsey00
04-21 21:12
江汉大学 电子信息类
点赞 评论 收藏
转发
点赞 7 评论
分享

招聘动态

查看更多

联易融2024届营销管培生校园招聘

小红书

24届春招&25届实习生招聘

24届春招硬件高薪职位集合

全站热榜

正在热议
# 牛客帮帮团来啦！有问必答 #
292967次浏览 6371人参与
# 我在牛爱网找对象 #
46007次浏览 291人参与
# 应届生应该先就业还是先择业 #
8862次浏览 96人参与
# 非技术岗薪资爆料 #
1543次浏览 72人参与
# 华为求职进展汇总 #
422946次浏览 4239人参与
# 来聊聊机械薪资天花板是哪家 #
13062次浏览 103人参与
# 第一次面试 #
7803次浏览 121人参与
# 为什么那么多公司毁约 #
30883次浏览 261人参与
# 数据人的面试交流地 #
160986次浏览 3533人参与
# 你觉得比亚迪今年还有春招吗？ #
34258次浏览 237人参与
# 找工作，你会甘心进小厂还是猛冲大厂 #
20135次浏览 193人参与
# 硬件兄弟们 甩出你的华为奖状 #
23917次浏览 163人参与
# 如果再来一次，你还会学硬件吗 #
16036次浏览 325人参与
# 租房前辈的忠告 #
19059次浏览 1543人参与
# 字节跳动工作体验 #
46060次浏览 1211人参与
# 机械人的薪资开到多少，才适合去？ #
36427次浏览 207人参与
# 机械人怎么评价今年的华为 #
45342次浏览 359人参与
# 你觉得通信/硬件有必要实习吗？ #
19372次浏览 393人参与
# 聊聊这家公司值得去吗 #
56947次浏览 955人参与
# 你已经投递多少份简历了 #
236477次浏览 3827人参与
牛客网
牛客企业服务