华为OD笔试之【回溯】2023Q1"/>
【限时免费】20天拿下华为OD笔试之【回溯】2023Q1
【回溯】2023Q1-硬件产品销售方案
题目描述与示例
题目描述
某公司目前推出了 AI 开发者套件、AI 加速卡、AI 加速模块、AI 服务器、智能边缘多种硬件产品,每种产品包含若干个型号。现某合作厂商要采购金额为 amount
元的硬件产品搭建自己的 AI 基座。假设当前库存有 N
种产品,每种产品的库存量充足,给定每种产品的价格,记为 price
(不存在价格相同的产品型号)。请为合作厂商列出所有可能的产品组合。
输入描述
输入包含采购金额 amount
和产品价格列表 price
。第一行为 amount
,第二行为 price
。例如:
输出描述
输出为组合列表。例如: [[500], [200, 300], [100, 200, 200], [100, 100, 300], [100, 100, 100, 200], [100, 100, 100, 100, 100]]
备注
- 对于给定输入,产品组合少于
150
种。输出的组合为一个数组,数组的每个元素也是一个数组,表示一种组合方案。如果给定产品无法组合金额为amount
元的方案,那么返回空列表。 - 两种组合方案,只要存在一种产品的数量不同,那么方案认为是不同的。
- 每种产品型号价格不相同
1 <= 产品类型数量 <= 30
100 <= 产品价格 <= 20000
100 <= 采购金额 <= 50000
示例一
输入
500
100, 200, 300, 500
输出
[[100, 100, 100, 100, 100], [100, 100, 100, 200], [100, 100, 300], [100, 200, 200], [200, 300], [500]]
示例二
输入
100
[100]
输出
[[100]]
解题思路
注意,本题和LC39. 组合总数完全一致,本质上是一道组合类型的回溯问题。
代码
# 题目:2023Q1-硬件产品销售方案
# 分值:200
# 作者:许老师-闭着眼睛学数理化
# 算法:回溯
# 代码看不懂的地方,请直接在群上提问total_sum = int(input())
nums = list(map(int, input().split(",")))# 初始化空的答案列表
ans = list()# 回溯函数
# nums: 题目给定的数字数组
# total_sum:题目给定的数字和
# ans: 答案数组
# path: 当前回溯的路径
# path_sum: 当前回溯的路径和
# startIdx: 本次递归中,nums数组中选择的开始索引
def dfs(nums, total_sum, ans, path, path_sum, startIdx):# 递归终止条件1:# 如果当前路径和path_sum >total_sum# 这条路径再往下搜寻没有意义,进行剪枝,终止当前路径继续往下搜寻if path_sum > total_sum:return# 递归终止条件2:# 如果当前路径和path_sum == total_sum,说明得到了一种组合方案# 将该种组合方案path加入ans即可,注意要使用切片或者拷贝if path_sum == total_sum:ans.append(path[:])return# 横向遍历nums中,从startIdx开始往后的所有索引for i in range(startIdx, len(nums)):# 获得i对应的数字numnum = nums[i]# 状态更新:# 1. 将num加入当前path数组中# 2. 将num加入当前path_sum路径和中path.append(num)path_sum += num# 回溯:由于num可能被反复选取,因此选择i作为下一个回溯的startIdxdfs(nums, total_sum, ans, path, path_sum, i)# 回滚:# 1. 将num从当前path数组弹出# 2. 将num从当前path_sum路径和中减去path.pop()path_sum -= num# 调用递归函数的入口,最开始path = [],path_sum = 0,startIdx = 0
dfs(nums, total_sum, ans, [], 0, 0)
print(ans)
时空复杂度
时间复杂度:O(N!)
。
空间复杂度:O(N)
。忽略调用递归函数时编译栈所占空间,仅考虑检查数组所占用空间。
进阶思考
如果本题并不要求列出所有情况,而只是要求计算出所有方案数,应该如何用更加简便的方法解决问题?
即LC377. 组合总数IV如何完成?
华为OD算法/大厂面试高频题算法练习冲刺训练
-
华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名!目前已服务100+同学成功上岸!
-
课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化
-
每期人数维持在20人内,保证能够最大限度地满足到每一个同学的需求,达到和1v1同样的学习效果!
-
60+天陪伴式学习,40+直播课时,300+动画图解视频,300+LeetCode经典题,200+华为OD真题/大厂真题,还有简历修改、模拟面试、专属HR对接将为你解锁
-
可上全网独家的欧弟OJ系统练习华子OD、大厂真题
-
可查看链接 大厂真题汇总 & OD真题汇总(持续更新)
-
绿色聊天软件戳
od1336
了解更多
更多推荐
【限时免费】20天拿下华为OD笔试之【回溯】2023Q1
发布评论