全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。
真题库：https://www.yuque.com/codernav.com/od
题目：硬件产品销售方案
知识点递归数组DFS搜索回溯
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
某公司目前推出了AI开发者套件、AI加速卡、AI加速模块、AI服务器、智能边缘多种硬件产品，每种产品包含若干个型号。现某合作厂商要采购金额为amount元的硬件产品搭建自己的AI基座。假设当前库存有N种产品，每种产品的库存量充足，给定每种产品的价格，记为price（不存在价格相同的产品型号）。请为合作厂商列出所有可能的产品组合。
输入描述：
输入包含采购金额amount和产品价格列表price。第一行为amount，第二行为price。例如：
500
[100, 200, 300, 500]
输出描述：
输出为组合列表。例如：
[[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
示例1
输入：
500
[100, 200, 300, 500, 500]
输出：
[[100, 100, 100, 100, 100], [100, 100, 100, 200], [100, 100, 300], [100, 200, 200], [200, 300], [500], [500]]
示例2
输入：
100
[100]
输出：
[[100]]
解题思路：
通过回溯求出所有可能的购买情况。
看例题，只统计等于预算的情况，而且集合没有排序的要求。
代码实现一：
package com.codernav.demo.hwod.exam;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* @title 硬件产品销售方案
* @Description 某公司目前推出了AI开发者套件、AI加速卡、AI加速模块、AI服务器、智能边缘多种硬件产品，每种产品包含若干个型号。
* 现某合作厂商要采购金额为amount元的硬件产品搭建自己的AI基座。
* 假设当前库存有N种产品，每种产品的库存量充足，给定每种产品的价格，记为price（不存在价格相同的产品型号）。
* 请为合作厂商列出所有可能的产品组合。
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/28
*/
public class Main {
public static int[] price; //物品价格数组
public static int amount; //预算
public static List<List<Integer>> resList = new ArrayList<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
amount = sc.nextInt();
sc.nextLine();
String[] strings = sc.nextLine().replace("[", "").replace("]", "").split(",");
price = new int[strings.length];
for (int i = 0; i < strings.length; i++) {
price[i] = Integer.parseInt(strings[i].trim());
}
handle(0, 0, new ArrayList<>());
System.out.println(resList);
}
/**
* 通过递归求出所有的购买情况
*
* @param index 物品价格索引
* @param count 购买物品总价格
* @param list 购买物品集合
*/
public static void handle(int index, int count, List<Integer> list) {
if (amount <= count) { //物品总价格大于等于预算总退出
//需要使用tempList，否则会影响入参中的list
List<Integer> tempList = new ArrayList<>(list);
if (amount == count) { //只统计等于预算的情况
resList.add(tempList);
}
} else {
for (int i = index; i < price.length; i++) {
list.add(price[i]);
handle(i, count + price[i], list);
list.remove(list.size() - 1);
}
}
}
}
代码实现二：Java满分代码实现
package com.codernav.demo.hwod.exam;
import java.util.*;
/**
* @title 硬件产品销售方案
* @Description 某公司目前推出了AI开发者套件、AI加速卡、AI加速模块、AI服务器、智能边缘多种硬件产品，每种产品包含若干个型号。
* 现某合作厂商要采购金额为amount元的硬件产品搭建自己的AI基座。
* 假设当前库存有N种产品，每种产品的库存量充足，给定每种产品的价格，记为price（不存在价格相同的产品型号）。
* 请为合作厂商列出所有可能的产品组合。
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/28
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int amount = Integer.parseInt(in.nextLine());
String input = in.nextLine().replaceAll("\\s", "");
input = input.substring(1, input.length() - 1);
String[] arr = input.split(",");
int[] prices = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
prices[i] = Integer.parseInt(arr[i]);
}
Arrays.sort(prices);
Stack<Integer> st = new Stack<>();
List<List<Integer>> ans = new ArrayList<>();
dfs(prices, amount, st, ans, 0);
System.out.println(ans);
}
public static void dfs(int[] prices, int amout, Stack<Integer> st, List<List<Integer>> ans, int index) {
if (amout == 0) {
ans.add(new ArrayList<Integer>(st));
return;
}
if (amout < prices[0]) return;
for (int i = index; i < prices.length; i++) {
int price = prices[i];
st.push(price);
dfs(prices, amout - price, st, ans, i);
st.pop();
}
}
}
相关文章
