跳至主要內容

2025A-硬件产品销售方案

题目描述与示例

题目描述

某公司目前推出了 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. 组合总数完全一致，本质上是一道组合类型的回溯问题。

代码

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频


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对应的数字num
        num = nums[i]
        # 状态更新：
        # 1. 将num加入当前path数组中
        # 2. 将num加入当前path_sum路径和中
        path.append(num)
        path_sum += num
        # 回溯：由于num可能被反复选取，因此选择i作为下一个回溯的startIdx
        dfs(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)

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取目标总和
        int totalSum = scanner.nextInt();
        scanner.nextLine(); // 处理换行符
        
        // 读取数组并分割为整数
        String[] numsStr = scanner.nextLine().split(", ");
        int[] nums = new int[numsStr.length];
        for (int i = 0; i < numsStr.length; i++) {
            nums[i] = Integer.parseInt(numsStr[i]);
        }
        
        // 初始化答案列表
        List<List<Integer>> ans = new ArrayList<>();
        
        // 调用回溯函数
        dfs(nums, totalSum, ans, new ArrayList<>(), 0, 0);
        
        // 输出结果
        System.out.println(ans);
    }

    // 回溯函数
    public static void dfs(int[] nums, int totalSum, List<List<Integer>> ans, List<Integer> path, int pathSum, int startIdx) {
        // 递归终止条件1：路径和大于目标总和
        if (pathSum > totalSum) {
            return;
        }
        
        // 递归终止条件2：路径和等于目标总和
        if (pathSum == totalSum) {
            ans.add(new ArrayList<>(path)); // 深拷贝
            return;
        }
        
        // 横向遍历nums中，从startIdx开始往后的所有索引
        for (int i = startIdx; i < nums.length; i++) {
            int num = nums[i];
            
            // 状态更新
            path.add(num);
            pathSum += num;
            
            // 回溯：由于num可能被反复选取，因此选择i作为下一个回溯的startIdx
            dfs(nums, totalSum, ans, path, pathSum, i);
            
            // 回滚
            path.remove(path.size() - 1);
            pathSum -= num;
        }
    }
}

C++

#include <iostream>
#include <vector>
#include <sstream>

using namespace std;

// 回溯函数
void dfs(vector<int>& nums, int totalSum, vector<vector<int>>& ans, vector<int>& path, int pathSum, int startIdx) {
    // 递归终止条件1：路径和大于目标总和
    if (pathSum > totalSum) {
        return;
    }
    
    // 递归终止条件2：路径和等于目标总和
    if (pathSum == totalSum) {
        ans.push_back(path); // 将当前路径加入答案中
        return;
    }
    
    // 横向遍历nums中，从startIdx开始往后的所有索引
    for (int i = startIdx; i < nums.size(); i++) {
        int num = nums[i];
        
        // 状态更新
        path.push_back(num);
        pathSum += num;
        
        // 回溯：由于num可能被反复选取，因此选择i作为下一个回溯的startIdx
        dfs(nums, totalSum, ans, path, pathSum, i);
        
        // 回滚
        path.pop_back();
        pathSum -= num;
    }
}

int main() {
    // 读取目标总和
    int totalSum;
    cin >> totalSum;
    cin.ignore(); // 处理换行符
    
    // 读取数组并分割为整数，考虑", "作为分割符
    vector<int> nums;
    string input;
    getline(cin, input);
    stringstream ss(input);
    string temp;
    while (getline(ss, temp, ',')) {
        if (temp[0] == ' ') { // 去掉前导空格
            temp = temp.substr(1);
        }
        nums.push_back(stoi(temp));
    }
    
    // 初始化答案列表
    vector<vector<int>> ans;
    
    // 调用回溯函数
    vector<int> path;
    dfs(nums, totalSum, ans, path, 0, 0);
    
    // 输出结果
    cout << "[";
    for (size_t i = 0; i < ans.size(); i++) {
        cout << "[";
        for (size_t j = 0; j < ans[i].size(); j++) {
            cout << ans[i][j];
            if (j < ans[i].size() - 1) {
                cout << ", ";
            }
        }
        cout << "]";
        if (i < ans.size() - 1) {
            cout << ", ";
        }
    }
    cout << "]" << endl;

    return 0;
}

C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

#define MAX_NUMS 1000
#define MAX_PATH 1000
#define MAX_RESULTS 10000

int nums[MAX_NUMS];            // 元素数组
int result[MAX_RESULTS][MAX_PATH]; // 存放结果的二维数组
int resultSizes[MAX_RESULTS]; // 结果中每一行的长度
int totalResultCount = 0;     // 总结果条数

int path[MAX_PATH];           // 当前路径
int pathSize = 0;

void dfs(int* nums, int numsSize, int totalSum, int pathSum, int startIdx) {
    if (pathSum > totalSum) return;
    if (pathSum == totalSum) {
        for (int i = 0; i < pathSize; i++) {
            result[totalResultCount][i] = path[i];
        }
        resultSizes[totalResultCount] = pathSize;
        totalResultCount++;
        return;
    }
    for (int i = startIdx; i < numsSize; i++) {
        int num = nums[i];
        path[pathSize++] = num;
        dfs(nums, numsSize, totalSum, pathSum + num, i); // 允许重复选择
        pathSize--;
    }
}

int main() {
    int totalSum;
    scanf("%d", &totalSum);
    getchar(); // 后续处理换行

    char input[1000];
    fgets(input, sizeof(input), stdin);

    int numsSize = 0;
    char* token = strtok(input, ",");
    while (token != NULL) {
        while (*token == ' ') token++; // 删除前缀空格
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",");
    }

    dfs(nums, numsSize, totalSum, 0, 0);

    // 格式化输出
    printf("[");
    for (int i = 0; i < totalResultCount; i++) {
        printf("[");
        for (int j = 0; j < resultSizes[i]; j++) {
            printf("%d", result[i][j]);
            if (j < resultSizes[i] - 1) printf(", ");
        }
        printf("]");
        if (i < totalResultCount - 1) printf(", ");
    }
    printf("]\n");

    return 0;
}

Node JavaScript

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

const inputLines = [];
rl.on("line", (line) => {
    inputLines.push(line.trim());
    if (inputLines.length === 2) {
        solve();
        rl.close();
    }
});

function solve() {
    const totalSum = parseInt(inputLines[0]); // 读取总和
    const nums = inputLines[1].split(", ").map(Number); // 转换为数组

    const ans = []; // 存放结果的列表

    // 回溯函数 dfs
    function dfs(path, pathSum, startIdx) {
        if (pathSum > totalSum) return; // 超过总和，直接退出
        if (pathSum === totalSum) {
            ans.push([...path]); // 深拷贝当前路径
            return;
        }

        for (let i = startIdx; i < nums.length; i++) {
            const num = nums[i];
            path.push(num); // 添加元素
            dfs(path, pathSum + num, i); // 允许重复选择，传入 i
            path.pop(); // 回溯清理
        }
    }

    dfs([], 0, 0);

    // 根据要求格式输出：通过手动组装
    const resultStr = '[' + ans.map(arr => '[' + arr.join(', ') + ']').join(', ') + ']';
    console.log(resultStr);
}

Go

package main

import (
        "bufio"
        "fmt"
        "os"
        "strconv"
        "strings"
)

// dfs 回溯函数
func dfs(nums []int, totalSum int, path []int, pathSum int, startIdx int, ans *[][]int) {
        if pathSum > totalSum {
                return
        }
        if pathSum == totalSum {
                temp := make([]int, len(path))
                copy(temp, path)
                *ans = append(*ans, temp)
                return
        }

        for i := startIdx; i < len(nums); i++ {
                path = append(path, nums[i])
                dfs(nums, totalSum, path, pathSum+nums[i], i, ans) // 允许重复选择
                path = path[:len(path)-1] // 回溯
        }
}

func main() {
        scanner := bufio.NewScanner(os.Stdin)

        // 读取总和
        scanner.Scan()
        totalSum, _ := strconv.Atoi(scanner.Text())

        // 读取数组
        scanner.Scan()
        parts := strings.Split(scanner.Text(), ", ")
        nums := make([]int, len(parts))
        for i, s := range parts {
                nums[i], _ = strconv.Atoi(s)
        }

        var ans [][]int
        dfs(nums, totalSum, []int{}, 0, 0, &ans)

        // 格式化输出：手动组装 JSON-like 格式
        fmt.Print("[")
        for i, comb := range ans {
                fmt.Print("[")
                for j, val := range comb {
                        fmt.Print(val)
                        if j < len(comb)-1 {
                                fmt.Print(", ")
                        }
                }
                fmt.Print("]")
                if i < len(ans)-1 {
                        fmt.Print(", ")
                }
        }
        fmt.Println("]")
}

时空复杂度

时间复杂度：O(N!)。

空间复杂度：O(N)。忽略调用递归函数时编译栈所占空间，仅考虑检查数组所占用空间。

本站内容包括机考真题解析、八股文速记、技术&行为面试指南、真实上岸经验与截图墙。
Copyright © 2025 欧弟算法