取数组中n个数之和为不大于目标值的最大值

admin1

1. #include <iostream>
2. #include <vector>
3. #include <algorithm>
5. std::pair<int, std::vector<int>> findMaxSumBelowLimit(const std::vector<double>& numbers, double limit) {
6.     std::pair<int, std::vector<int>> bestSumAndCombination{0, {}};
8.     std::vector<bool> used(numbers.size(), false);
9.     std::vector<int> combination;
11.     backtrack(numbers, limit, used, combination, 0, 0, bestSumAndCombination);
13.     return bestSumAndCombination;
14. }
16. void backtrack(const std::vector<double>& numbers, double limit, std::vector<bool>& used,
17.                std::vector<int>& combination, size采用t index, int currentSum,
18.                std::pair<int, std::vector<int>>& bestSumAndCombination) {
19.     if (currentSum > limit) {
20.         return; // 如果当前和大于限制，直接返回
21.     }
23.     if (index == numbers.size()) {
24.         if (currentSum > bestSumAndCombination.first) {
25.             bestSumAndCombination.first = currentSum;
26.             bestSumAndCombination.second = combination;
27.         }
28.         return;
29.     }
31.     // 不选当前数
32.     backtrack(numbers, limit, used, combination, index + 1, currentSum, bestSumAndCombination);
34.     // 选当前数
35.     if (!used[index]) {
36.         used[index] = true;
37.         combination.push采用back(index);
38.         backtrack(numbers, limit, used, combination, index + 1, currentSum + static采用cast<int>(numbers[index]), bestSumAndCombination);
39.         used[index] = false;
40.         combination.pop采用back();
41.     }
42. }
44. int main() {
45.     std::vector<double> numbers = {1, 2, 5, 16.3, 22.7, 32.6, 40, 53.1};
46.     double limit = 100;
47.    
48.     auto result = findMaxSumBelowLimit(numbers, limit);
49.    
50.     std::cout << "The maximum sum within the limit is: " << result.first << std::endl;
51.     std::cout << "The combination with this sum is: [";
52.     for (size采用t i : result.second) {
53.         std::cout << numbers[i] << " ";
54.     }
55.     std::cout << "]" << std::endl;
57.     return 0;
58. }

复制代码

admin1

1. static  std::pair<double, std::vector<double>> findMaxSumBelowLimit(const std::vector<double>& numbers, double limit) {
2.         std::vector<double> temp;
3.         std::pair<double, std::vector<double>> bestSumAndCombination;
4.         bestSumAndCombination=(std::make采用pair(1, temp));
7.         std::vector<bool> used(numbers.size(), false);
8.         std::vector<double> combination;
10.         backtrack(numbers, limit, used, combination, 0, 0, bestSumAndCombination);
12.         return bestSumAndCombination;
13. }
15. static void backtrack(const std::vector<double>& numbers, double limit, std::vector<bool>& used,
16.                            std::vector<double>& combination, int index, double currentSum,
17.                            std::pair<double, std::vector<double>>& bestSumAndCombination) {
18.                                    if (currentSum > limit) {
19.                                            return; // 如果当前和大于限制，直接返回
20.                                    }
22.                                    if (index == numbers.size()) {
23.                                            if (currentSum > bestSumAndCombination.first) {
24.                                                    bestSumAndCombination.first = currentSum;
25.                                                    bestSumAndCombination.second = combination;
26.                                            }
27.                                            return;
28.                                    }
30.                                    // 不选当前数
31.                                    backtrack(numbers, limit, used, combination, index + 1, currentSum, bestSumAndCombination);
33.                                    // 选当前数
34.                                    if (!used[index]) {
35.                                            used[index] = true;
36.                                            combination.push采用back( numbers[index]  );
37.                                            backtrack(numbers, limit, used, combination, index + 1, currentSum + numbers[index] , bestSumAndCombination);
38.                                            used[index] = false;
39.                                            combination.pop采用back();
40.                                    }
41. }
43.                 vector<double> sssa{20.1，19.3，15.4，13.3，10.3，9.1}
44.                 double limit = 100.15;
45.                 auto result = findMaxSumBelowLimit(sssa, limit);

复制代码