一、问题描述
题目描述
某公司目前推出了AI开发者套件,AI加速卡,AI加速模块,AI服务器,智能边缘多种硬件产品,每种产品包含若干个型号。
现某合作厂商要采购金额为amount
元的硬件产品搭建自己的AI基座。
例如当前库存有N
种产品,每种产品的库存量充足,给定每种产品的价格,记为price
(不存在价格相同的产品型号)。
请为合作厂商列出所有可能的产品组合。
输入描述
输入包含采购金额amount
和产品价格列表price
。第一行为amount
,第二行为price
,例如:
500
[100, 200, 300, 500]
输出描述
输出为组合列表。例如:
[[100, 100, 100, 100, 100], [100, 100, 100, 200], [100, 100, 300], [100, 200, 200], [200, 300], [500]]
用例
用例 1
输入:
500
[100, 200, 300, 500]
输出:
[[100, 100, 100, 100, 100], [100, 100, 100, 200], [100, 100, 300], [100, 200, 200], [200, 300], [500]]
用例 2
输入:
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]]
题目解析
简单的可重复元素组合求解。
详细步骤
-
读取输入:
- 读取采购金额
amount
。 - 读取产品价格列表
price
。
- 读取采购金额
-
初始化结果列表:
- 创建一个空列表
result
,用于存储所有可能的产品组合。
- 创建一个空列表
-
递归函数:
- 定义一个递归函数
findCombinations
,参数包括:start
:当前开始的索引。target
:当前剩余的金额。path
:当前的组合路径。
- 如果
target
为 0,将path
添加到result
中。 - 如果
target
小于 0,返回。 - 从
start
开始遍历price
,对于每个价格p
:- 递归调用
findCombinations
,更新target
为target - p
,path
为path + [p]
。
- 递归调用
- 定义一个递归函数
-
调用递归函数:
- 调用
findCombinations(0, amount, [])
。
- 调用
-
输出结果:
- 输出
result
。
- 输出
用例解释
用例 1
- 输入:
amount = 500
price = [100, 200, 300, 500]
- 输出:
[[100, 100, 100, 100, 100], [100, 100, 100, 200], [100, 100, 300], [100, 200, 200], [200, 300], [500]]
解释:
- 递归函数会尝试所有可能的组合,直到找到所有满足条件的组合。
用例 2
- 输入:
amount = 500
price = [100, 200, 300, 500, 500]
- 输出:
[[100, 100, 100, 100, 100], [100, 100, 100, 200], [100, 100, 300], [100, 200, 200], [200, 300], [500], [500]]
解释:
- 递归函数会尝试所有可能的组合,直到找到所有满足条件的组合。
通过上述步骤,我们可以高效地求出所有可能的产品组合。这种方法的时间复杂度为 O(2^n)
,其中 n
是产品价格列表的长度。
二、JavaScript算法源码
以下是带有详细中文注释和讲解的 JavaScript 代码:
JavaScript 代码
// 引入 readline 模块,用于从控制台读取输入
const readline = require("readline");
// 创建 readline 接口
const rl = readline.createInterface({
input: process.stdin, // 输入流为标准输入
output: process.stdout, // 输出流为标准输出
});
// 定义一个数组 lines,用于存储输入的行
const lines = [];
// 监听 'line' 事件,当用户输入一行时触发
rl.on("line", (line) => {
// 将输入的行添加到 lines 数组中
lines.push(line);
// 当 lines 数组中有两行输入时,开始处理
if (lines.length === 2) {
// 解析输入
const amount = lines[0] - 0; // 将第一行转换为数字,表示目标金额
const prices = JSON.parse(lines[1]); // 将第二行解析为数组,表示可选的价格列表
// 调用 getResult 函数计算结果,并输出
console.log(getResult(amount, prices));
// 清空 lines 数组,以便处理下一组输入
lines.length = 0;
}
});
// 定义 getResult 函数,用于计算所有可能的组合
function getResult(amount, prices) {
const res = []; // 用于存储所有符合条件的组合
dfs(amount, prices, 0, 0, [], res); // 调用深度优先搜索函数
return `[${res.join(", ")}]`; // 将结果格式化为字符串并返回
}
// 定义深度优先搜索函数 dfs
function dfs(total, arr, index, sum, path, res) {
// 如果当前总和 sum 大于或等于目标金额 total,则停止递归
if (sum >= total) {
// 如果当前总和 sum 等于目标金额 total,则将当前路径 path 添加到结果 res 中
if (sum === total) res.push(`[${path.join(", ")}]`);
return;
}
// 遍历数组 arr,从 index 开始
for (let i = index; i < arr.length; i++) {
path.push(arr[i]); // 将当前元素添加到路径 path 中
dfs(total, arr, i, sum + arr[i], path, res); // 递归调用 dfs
path.pop(); // 回溯:移除路径 path 中的最后一个元素
}
}
代码讲解:
1. 输入获取部分:
readline
模块:- 用于从控制台读取输入。
- 通过
rl.on('line', callback)
监听用户输入。
lines
数组:- 用于存储用户输入的行。
- 当
lines
数组中有两行输入时,开始处理。
2. 输入解析:
amount
:- 从
lines[0]
中获取目标金额,并将其转换为数字。
- 从
prices
:- 从
lines[1]
中获取价格列表,并使用JSON.parse()
将其解析为数组。
- 从
3. 核心逻辑部分:
getResult
函数:- 调用深度优先搜索函数
dfs
,计算所有可能的组合。 - 将结果格式化为字符串并返回。
- 调用深度优先搜索函数
dfs
函数:- 使用深度优先搜索算法遍历所有可能的组合。
- 参数说明:
total
:目标金额。arr
:可选的价格列表。index
:当前遍历的起始位置。sum
:当前路径的总和。path
:当前路径。res
:存储所有符合条件的组合。
- 递归终止条件:
- 如果当前总和
sum
大于或等于目标金额total
,则停止递归。 - 如果当前总和
sum
等于目标金额total
,则将当前路径path
添加到结果res
中。
- 如果当前总和
- 递归调用:
- 遍历数组
arr
,从index
开始。 - 将当前元素添加到路径
path
中,并递归调用dfs
。 - 回溯:移除路径
path
中的最后一个元素。
- 遍历数组
4. 示例运行:
输入 1:
5
[1, 2, 5]
- 输出:
[[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2], [5]]
输入 2:
3
[1]
- 输出:
[[1, 1, 1]]
输入 3:
0
[1, 2, 3]
- 输出:
[]
总结:
- 该代码通过深度优先搜索算法,计算所有可能的组合,使得组合的总和等于目标金额。
- 代码逻辑清晰,注释详细,适合学习和参考。
如果有其他问题,欢迎继续提问!
三、Java算法源码
以下是带有详细中文注释和讲解的 Java 代码:
Java 代码
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// 创建 Scanner 对象,用于从控制台读取输入
Scanner sc = new Scanner(System.in);
// 读取目标金额 amount
int amount = Integer.parseInt(sc.nextLine());
// 读取价格列表的字符串形式
String str = sc.nextLine();
// 将字符串解析为 Integer 数组
Integer[] prices =
Arrays.stream(str.substring(1, str.length() - 1).split(", ")) // 去掉首尾的方括号,并按 ", " 分割
.map(Integer::parseInt) // 将每个字符串转换为整数
.toArray(Integer[]::new); // 转换为 Integer 数组
// 调用 getResult 函数计算结果,并输出
System.out.println(getResult(amount, prices));
}
// 定义 getResult 函数,用于计算所有可能的组合
public static String getResult(int amount, Integer[] prices) {
ArrayList<String> res = new ArrayList<>(); // 用于存储所有符合条件的组合
LinkedList<Integer> path = new LinkedList<>(); // 用于存储当前路径
// 调用深度优先搜索函数 dfs
dfs(amount, prices, 0, 0, path, res);
// 将结果转换为字符串并返回
return res.toString();
}
// 定义深度优先搜索函数 dfs
public static void dfs(
int total, // 目标金额
Integer[] arr, // 可选的价格列表
int index, // 当前遍历的起始位置
int sum, // 当前路径的总和
LinkedList<Integer> path, // 当前路径
ArrayList<String> res // 存储所有符合条件的组合
) {
// 如果当前总和 sum 大于或等于目标金额 total,则停止递归
if (sum >= total) {
// 如果当前总和 sum 等于目标金额 total,则将当前路径 path 添加到结果 res 中
if (sum == total) res.add(path.toString());
return;
}
// 遍历数组 arr,从 index 开始
for (int i = index; i < arr.length; i++) {
path.addLast(arr[i]); // 将当前元素添加到路径 path 中
dfs(total, arr, i, sum + arr[i], path, res); // 递归调用 dfs
path.removeLast(); // 回溯:移除路径 path 中的最后一个元素
}
}
}
代码讲解:
1. 输入获取部分:
Scanner
对象:- 用于从控制台读取输入。
amount
:- 从输入中读取目标金额,并将其转换为整数。
prices
:- 从输入中读取价格列表的字符串形式。
- 使用
substring()
去掉首尾的方括号,并按", "
分割。 - 使用
map()
将每个字符串转换为整数。 - 使用
toArray()
转换为Integer
数组。
2. 核心逻辑部分:
getResult
函数:- 调用深度优先搜索函数
dfs
,计算所有可能的组合。 - 将结果转换为字符串并返回。
- 调用深度优先搜索函数
dfs
函数:- 使用深度优先搜索算法遍历所有可能的组合。
- 参数说明:
total
:目标金额。arr
:可选的价格列表。index
:当前遍历的起始位置。sum
:当前路径的总和。path
:当前路径。res
:存储所有符合条件的组合。
- 递归终止条件:
- 如果当前总和
sum
大于或等于目标金额total
,则停止递归。 - 如果当前总和
sum
等于目标金额total
,则将当前路径path
添加到结果res
中。
- 如果当前总和
- 递归调用:
- 遍历数组
arr
,从index
开始。 - 将当前元素添加到路径
path
中,并递归调用dfs
。 - 回溯:移除路径
path
中的最后一个元素。
- 遍历数组
3. 示例运行:
输入 1:
5
[1, 2, 5]
- 输出:
[[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2], [5]]
输入 2:
3
[1]
- 输出:
[[1, 1, 1]]
输入 3:
0
[1, 2, 3]
- 输出:
[]
总结:
- 该代码通过深度优先搜索算法,计算所有可能的组合,使得组合的总和等于目标金额。
- 代码逻辑清晰,注释详细,适合学习和参考。
如果有其他问题,欢迎继续提问!
四、Python算法源码
以下是带有详细中文注释和讲解的 Python 代码:
Python 代码
# 从输入中读取目标金额 amount
amount = int(input())
# 从输入中读取价格列表 prices
prices = eval(input())
# 定义深度优先搜索函数 dfs
def dfs(total, arr, index, sum, path, res):
"""
深度优先搜索函数,用于计算所有可能的组合。
参数:
- total: 目标金额
- arr: 可选的价格列表
- index: 当前遍历的起始位置
- sum: 当前路径的总和
- path: 当前路径
- res: 存储所有符合条件的组合
"""
# 如果当前总和 sum 大于或等于目标金额 total,则停止递归
if sum >= total:
# 如果当前总和 sum 等于目标金额 total,则将当前路径 path 添加到结果 res 中
if sum == total:
res.append(path[:]) # 使用 path[:] 创建 path 的副本,避免后续修改影响结果
return
# 遍历数组 arr,从 index 开始
for i in range(index, len(arr)):
path.append(arr[i]) # 将当前元素添加到路径 path 中
dfs(total, arr, i, sum + arr[i], path, res) # 递归调用 dfs
path.pop() # 回溯:移除路径 path 中的最后一个元素
# 定义结果列表 res
res = []
# 调用 dfs 函数计算结果
dfs(amount, prices, 0, 0, [], res)
# 输出结果
print(res)
代码讲解:
1. 输入获取部分:
amount
:- 从输入中读取目标金额,并将其转换为整数。
prices
:- 从输入中读取价格列表,并使用
eval()
将其解析为列表。
- 从输入中读取价格列表,并使用
2. 核心逻辑部分:
dfs
函数:- 使用深度优先搜索算法遍历所有可能的组合。
- 参数说明:
total
:目标金额。arr
:可选的价格列表。index
:当前遍历的起始位置。sum
:当前路径的总和。path
:当前路径。res
:存储所有符合条件的组合。
- 递归终止条件:
- 如果当前总和
sum
大于或等于目标金额total
,则停止递归。 - 如果当前总和
sum
等于目标金额total
,则将当前路径path
添加到结果res
中。
- 如果当前总和
- 递归调用:
- 遍历数组
arr
,从index
开始。 - 将当前元素添加到路径
path
中,并递归调用dfs
。 - 回溯:移除路径
path
中的最后一个元素。
- 遍历数组
3. 示例运行:
输入 1:
5
[1, 2, 5]
- 输出:
[[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2], [5]]
输入 2:
3
[1]
- 输出:
[[1, 1, 1]]
输入 3:
0
[1, 2, 3]
- 输出:
[]
总结:
- 该代码通过深度优先搜索算法,计算所有可能的组合,使得组合的总和等于目标金额。
- 代码逻辑清晰,注释详细,适合学习和参考。
如果有其他问题,欢迎继续提问!
五、C/C++算法源码:
以下是 C++ 和 C 语言的代码实现,并附带详细的中文注释和讲解:
C++ 代码
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;
// 定义深度优先搜索函数 dfs
void dfs(int total, vector<int>& arr, int index, int sum, vector<int>& path, vector<vector<int>>& res) {
/**
* 深度优先搜索函数,用于计算所有可能的组合。
*
* 参数:
* - total: 目标金额
* - arr: 可选的价格列表
* - index: 当前遍历的起始位置
* - sum: 当前路径的总和
* - path: 当前路径
* - res: 存储所有符合条件的组合
*/
// 如果当前总和 sum 大于或等于目标金额 total,则停止递归
if (sum >= total) {
// 如果当前总和 sum 等于目标金额 total,则将当前路径 path 添加到结果 res 中
if (sum == total) {
res.push_back(path);
}
return;
}
// 遍历数组 arr,从 index 开始
for (int i = index; i < arr.size(); i++) {
path.push_back(arr[i]); // 将当前元素添加到路径 path 中
dfs(total, arr, i, sum + arr[i], path, res); // 递归调用 dfs
path.pop_back(); // 回溯:移除路径 path 中的最后一个元素
}
}
// 定义 getResult 函数,用于计算结果
vector<vector<int>> getResult(int amount, vector<int>& prices) {
vector<vector<int>> res; // 用于存储所有符合条件的组合
vector<int> path; // 用于存储当前路径
dfs(amount, prices, 0, 0, path, res); // 调用深度优先搜索函数 dfs
return res;
}
int main() {
int amount;
cin >> amount; // 读取目标金额 amount
cin.ignore(); // 忽略换行符
string str;
getline(cin, str); // 读取价格列表的字符串形式
// 将字符串解析为整数数组
vector<int> prices;
stringstream ss(str.substr(1, str.length() - 2)); // 去掉首尾的方括号
string token;
while (getline(ss, token, ',')) {
prices.push_back(stoi(token)); // 将每个字符串转换为整数并添加到 prices 中
}
// 调用 getResult 函数计算结果
vector<vector<int>> result = getResult(amount, prices);
// 输出结果
cout << "[";
for (size_t i = 0; i < result.size(); i++) {
cout << "[";
for (size_t j = 0; j < result[i].size(); j++) {
cout << result[i][j];
if (j < result[i].size() - 1) cout << ", ";
}
cout << "]";
if (i < result.size() - 1) cout << ", ";
}
cout << "]" << endl;
return 0;
}
C 语言代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 1000
// 定义深度优先搜索函数 dfs
void dfs(int total, int* arr, int arrSize, int index, int sum, int* path, int pathSize, int** res, int* returnSize, int* returnColumnSizes) {
/**
* 深度优先搜索函数,用于计算所有可能的组合。
*
* 参数:
* - total: 目标金额
* - arr: 可选的价格列表
* - arrSize: 价格列表的长度
* - index: 当前遍历的起始位置
* - sum: 当前路径的总和
* - path: 当前路径
* - pathSize: 当前路径的长度
* - res: 存储所有符合条件的组合
* - returnSize: 结果的总数
* - returnColumnSizes: 每个结果的长度
*/
// 如果当前总和 sum 大于或等于目标金额 total,则停止递归
if (sum >= total) {
// 如果当前总和 sum 等于目标金额 total,则将当前路径 path 添加到结果 res 中
if (sum == total) {
res[*returnSize] = (int*)malloc(pathSize * sizeof(int));
memcpy(res[*returnSize], path, pathSize * sizeof(int));
returnColumnSizes[*returnSize] = pathSize;
(*returnSize)++;
}
return;
}
// 遍历数组 arr,从 index 开始
for (int i = index; i < arrSize; i++) {
path[pathSize] = arr[i]; // 将当前元素添加到路径 path 中
dfs(total, arr, arrSize, i, sum + arr[i], path, pathSize + 1, res, returnSize, returnColumnSizes); // 递归调用 dfs
}
}
// 定义 getResult 函数,用于计算结果
int** getResult(int amount, int* prices, int pricesSize, int* returnSize, int** returnColumnSizes) {
int** res = (int**)malloc(MAX_SIZE * sizeof(int*)); // 用于存储所有符合条件的组合
*returnColumnSizes = (int*)malloc(MAX_SIZE * sizeof(int)); // 用于存储每个结果的长度
*returnSize = 0; // 初始化结果的总数
int* path = (int*)malloc(MAX_SIZE * sizeof(int)); // 用于存储当前路径
dfs(amount, prices, pricesSize, 0, 0, path, 0, res, returnSize, *returnColumnSizes); // 调用深度优先搜索函数 dfs
free(path); // 释放 path 的内存
return res;
}
int main() {
int amount;
scanf("%d", &amount); // 读取目标金额 amount
getchar(); // 忽略换行符
char str[MAX_SIZE];
fgets(str, MAX_SIZE, stdin); // 读取价格列表的字符串形式
// 将字符串解析为整数数组
int prices[MAX_SIZE];
int pricesSize = 0;
char* token = strtok(str, "[], "); // 去掉首尾的方括号,并按 ", " 分割
while (token != NULL) {
prices[pricesSize++] = atoi(token); // 将每个字符串转换为整数并添加到 prices 中
token = strtok(NULL, "[], ");
}
int returnSize; // 结果的总数
int* returnColumnSizes; // 每个结果的长度
// 调用 getResult 函数计算结果
int** result = getResult(amount, prices, pricesSize, &returnSize, &returnColumnSizes);
// 输出结果
printf("[");
for (int i = 0; i < returnSize; i++) {
printf("[");
for (int j = 0; j < returnColumnSizes[i]; j++) {
printf("%d", result[i][j]);
if (j < returnColumnSizes[i] - 1) printf(", ");
}
printf("]");
if (i < returnSize - 1) printf(", ");
}
printf("]\n");
// 释放内存
for (int i = 0; i < returnSize; i++) {
free(result[i]);
}
free(result);
free(returnColumnSizes);
return 0;
}
代码讲解:
1. 输入获取部分:
- C++:
- 使用
cin
读取目标金额amount
。 - 使用
getline
读取价格列表的字符串形式,并通过stringstream
解析为整数数组。
- 使用
- C:
- 使用
scanf
读取目标金额amount
。 - 使用
fgets
读取价格列表的字符串形式,并通过strtok
解析为整数数组。
- 使用
2. 核心逻辑部分:
dfs
函数:- 使用深度优先搜索算法遍历所有可能的组合。
- 参数说明:
total
:目标金额。arr
:可选的价格列表。index
:当前遍历的起始位置。sum
:当前路径的总和。path
:当前路径。res
:存储所有符合条件的组合。
- 递归终止条件:
- 如果当前总和
sum
大于或等于目标金额total
,则停止递归。 - 如果当前总和
sum
等于目标金额total
,则将当前路径path
添加到结果res
中。
- 如果当前总和
- 递归调用:
- 遍历数组
arr
,从index
开始。 - 将当前元素添加到路径
path
中,并递归调用dfs
。 - 回溯:移除路径
path
中的最后一个元素。
- 遍历数组
3. 示例运行:
输入 1:
5
[1, 2, 5]
- 输出:
[[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2], [5]]
输入 2:
3
[1]
- 输出:
[[1, 1, 1]]
输入 3:
0
[1, 2, 3]
- 输出:
[]
总结:
- C++ 和 C 代码通过深度优先搜索算法,计算所有可能的组合,使得组合的总和等于目标金额。
- 代码逻辑清晰,注释详细,适合学习和参考。
如果有其他问题,欢迎继续提问!
标签:200,Java,Python,res,sum,int,path,100,total From: https://blog.csdn.net/m0_63168877/article/details/145099761