某公司目前推出了AI开发者套件、AI加速卡、AI加速模块、AI服务器、智能边缘多种硬件产品，每种产品包含若干个型号。
现某合作厂商要采购金额为amount元的硬件产品搭建自己的AI基座。
假设当前库存有 种产品，每种产品的库存量充足，给定每种产品的价格，记为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]]
amount元的方案，那么返回空列表。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]]
100
[100]
[[100]]
这个问题的目标是找出给定价格列表中，所有可以组合成指定采购金额的方案。为了解决这个问题，我们使用了递归回溯算法。回溯算法的核心思想是尝试从当前状态向下一个状态转换，如果满足约束条件，那么就递归调用自身进行下一步尝试，否则就回溯到上一个状态。在这个问题中，我们需要在给定的价格列表中找到所有可以组合成指定金额的方案。
具体来说，我们从价格列表的第一个元素开始，尝试将其添加到当前组合中。接着，我们减去当前元素的价格，并递归地尝试添加下一个元素。如果剩余金额为0，说明我们找到了一个有效的组合，将其添加到结果列表中。如果剩余金额小于0，说明当前组合无法满足金额要求，我们需要回溯。在回溯过程中，我们将当前元素从组合中移除，并尝试下一个元素。
为了避免重复计算，我们使用一个参数 start 来记录当前元素在价格列表中的位置。这样，在递归调用时，我们只会尝试从当前元素开始的子列表。在每一轮递归中，我们都会遍历价格列表中的所有元素，尝试添加它们到组合中。因此，这个算法的时间复杂度主要取决于递归树的深度和每一层的分支数量。
对于这个问题，递归树的深度最大为 amount / min(price)，其中 min(price) 表示价格列表中的最小值。在最坏情况下，我们需要尝试所有可能的组合，即每一层都有 n 个分支，其中 n 为价格列表的长度。因此，时间复杂度最大为 O(n^(amount / min(price)))。由于题目限制了产品类型数量和价格范围，所以这个算法在实际情况下的运行时间是可接受的。
空间复杂度主要取决于递归调用的栈空间和结果列表的大小。在最坏情况下，递归栈的深度为 amount / min(price)，因此空间复杂度为 O(amount / min(price))。此外，我们还需要存储所有有效的组合，这需要额外的空间。由于给定的输入限制，我们可以保证输出的组合数量不会超过150种，因此空间复杂度是可以接受的。
#include <stdio.h>
#include <stdlib.h>
void find_combinations(int amount, int *price, int n, int start, int *combination, int index, int *combination_count) {
if (amount == 0) {
for (int i = 0; i < index; i++) {
printf("%d", combination[i]);
if (i < index - 1) {
printf(", ");
}
}
printf("]\n");
(*combination_count)++;
return;
}
for (int i = start; i < n; i++) {
if (amount >= price[i]) {
combination[index] = price[i];
find_combinations(amount - price[i], price, n, i, combination, index + 1, combination_count);
}
}
}
int main() {
int amount;
scanf("%d", &amount);
int n;
scanf("%d", &n);
int *price = (int *)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
scanf("%d", &price[i]);
}
printf("[\n");
int *combination = (int *)malloc(amount * sizeof(int));
int combination_count = 0;
find_combinations(amount, price, n, 0, combination, 0, &combination_count);
printf("]\n");
free(price);
free(combination);
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
void find_combinations(int amount, const vector<int>& price, int start, vector<int>& combination, int& combination_count) {
if (amount == 0) {
cout << "[";
for (int i = 0; i < combination.size(); i++) {
cout << combination[i];
if (i < combination.size() - 1) {
cout << ", ";
}
}
cout << "]," << endl;
combination_count++;
return;
}
for (int i = start; i < price.size(); i++) {
if (amount >= price[i]) {
combination.push_back(price[i]);
find_combinations(amount - price[i], price, i, combination, combination_count);
combination.pop_back();
}
}
}
int main() {
int amount;
cin >> amount;
int n;
cin >> n;
vector<int> price(n);
for (int i = 0; i < n; i++) {
cin >> price[i];
}
cout << "[" << endl;
vector<int> combination;
int combination_count = 0;
find_combinations(amount, price, 0, combination, combination_count);
cout << "]" << endl;
return 0;
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
/**
* Created with IntelliJ IDEA.
* <br>Author: Amos
* <br>E-mail: amos@amoscloud.com
* <br>Date: 2023/3/16
* <br>Time: 8:46
* <br>Description:
*/
public class Main0228 {
public static void main(String[] args) {
try (Scanner scanner = new Scanner(System.in)) {
int amount = scanner.nextInt();
scanner.nextLine();
String line = scanner.nextLine();
String res = solution(amount, line);
System.out.println(res);
}
}
private static String solution(int amount, String line) {
Integer[] price = Arrays.stream(line.substring(1, line.length() - 1).split("\\W+"))
.map(Integer::parseInt)
.toArray(Integer[]::new);
ArrayList<String> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
dfs(amount, price, 0, 0, path, res);
return res.toString();
}
private static void dfs(
int total,
Integer[] arr,
int index,
int sum,
LinkedList<Integer> path,
ArrayList<String> res) {
if (sum >= total) {
if (sum == total) res.add(path.toString());
return;
}
for (int i = index; i < arr.length; i++) {
path.addLast(arr[i]);
dfs(total, arr, i, sum + arr[i], path, res);
path.removeLast();
}
}
}
from typing import List
def find_combinations(amount: int, price: List[int], start: int, combination: List[int], combinations: List[List[int]]) -> None:
if amount == 0:
combinations.append(list(combination))
return
for i in range(start, len(price)):
if amount >= price[i]:
combination.append(price[i])
find_combinations(amount - price[i], price, i, combination, combinations)
combination.pop()
def main():
amount = int(input())
price = list(map(int, input().split()))
combinations = []
find_combinations(amount, price, 0, [], combinations)
print(combinations)
if __name__ == '__main__':
main()
const readline = require('readline');
function find_combinations(amount, price, start, combination, combinations) {
if (amount === 0) {
combinations.push([...combination]);
return;
}
for (let i = start; i < price.length; i++) {
if (amount >= price[i]) {
combination.push(price[i]);
find_combinations(amount - price[i], price, i, combination, combinations);
combination.pop();
}
}
}
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
const input = [];
rl.on('line', (line) => {
input.push(line);
if (input.length === 2) {
rl.close();
}
}).on('close', () => {
const amount = parseInt(input[0]);
const price = input[1].split(' ').map(Number);
const combinations = [];
find_combinations(amount, price, 0, [], combinations);
console.log(combinations);
});
package main
import (
"fmt"
"strings"
"strconv"
)
func find_combinations(amount int, price []int, start int, combination []int, combinations *[][]int) {
if amount == 0 {
*combinations = append(*combinations, append([]int{}, combination...))
return
}
for i := start; i < len(price); i++ {
if amount >= price[i] {
combination = append(combination, price[i])
find_combinations(amount-price[i], price, i, combination, combinations)
combination = combination[:len(combination)-1]
}
}
}
func main() {
var amount int
fmt.Scan(&amount)
var priceStr string
fmt.Scan(&priceStr)
priceStrs := strings.Split(priceStr, " ")
price := make([]int, len(priceStrs))
for i, p := range priceStrs {
price[i], _ = strconv.Atoi(p)
}
combinations := [][]int{}
find_combinations(amount, price, 0, []int{}, &combinations)
fmt.Println(combinations)
}