西安网站设计开发人才在线网站排名工具

【回溯】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]]

备注

1. 对于给定输入，产品组合少于 150 种。输出的组合为一个数组，数组的每个元素也是一个数组，表示一种组合方案。如果给定产品无法组合金额为 amount 元的方案，那么返回空列表。
2. 两种组合方案，只要存在一种产品的数量不同，那么方案认为是不同的。
3. 每种产品型号价格不相同
4. 1 <= 产品类型数量 <= 30
5. 100 <= 产品价格 <= 20000
6. 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了解更多