找到满足条件的元素组合

admin1

对于给定的std::vector<double> a = {1.0, 2.5, 3.7}和std::vector<double> b = {4.2, 5.0, 6.8}，以及阈值l = 10，调用findMaxSumCombination(a, b, l)将返回std::vector<double> c = {1.0, 5.0, 3.7}，其中c的和等于9.7，最大且小于l=10。

1. #include <iostream>
   
2. #include <vector>
   
3. 
   
4. void backtrack(const std::vector<double>& a, const std::vector<double>& b, std::vector<double>& c, int index, double sum, double threshold, double& maxSum) {
   
5.     if (sum > threshold) {
   
6.         return;  // 当前组合的和已经大于阈值，剪枝
   
7.     }
   
8.    
   
9.     if (sum > maxSum) {
   
10.         maxSum = sum;  // 更新最大和
    
11.     }
    
12.    
    
13.     if (index >= a.size() && index >= b.size()) {
    
14.         return;  // 已经遍历完所有元素，结束递归
    
15.     }
    
16.    
    
17.     if (index < a.size()) {
    
18.         c.push_back(a[index]);  // 将a中的元素加入组合c
    
19.         backtrack(a, b, c, index + 1, sum + a[index], threshold, maxSum);
    
20.         c.pop_back();  // 回溯，将a中的元素移出组合c
    
21.     }
    
22.    
    
23.     if (index < b.size()) {
    
24.         c.push_back(b[index]);  // 将b中的元素加入组合c
    
25.         backtrack(a, b, c, index + 1, sum + b[index], threshold, maxSum);
    
26.         c.pop_back();  // 回溯，将b中的元素移出组合c
    
27.     }
    
28. }
    
29. 
    
30. std::vector<double> findMaxSumCombination(const std::vector<double>& a, const std::vector<double>& b, double threshold) {
    
31.     std::vector<double> c;
    
32.     double maxSum = 0.0;
    
33.     backtrack(a, b, c, 0, 0.0, threshold, maxSum);
    
34.     return c;
    
35. }

复制代码

1. // 回溯函数，寻找给定向量vec中元素的最大和组合，不超过阈值l
   
2. static bool backtrack(std::vector<double>& result, const std::vector<double>& vec, size_t index, double sum, double l) {
   
3.         // 基本情况：如果当前和等于阈值，说明找到了一个有效的组合
   
4.         if (sum == l) {
   
5.                 result = vec;
   
6.                 return true;
   
7.         }
   
8. 
   
9.         // 遍历向量中剩余的元素
   
10.         for (size_t i = index; i < vec.size(); ++i) {
    
11.                 // 跳过那些加上当前和会超过阈值的元素
    
12.                 if (sum + vec[i] > l) {
    
13.                         continue;
    
14.                 }
    
15. 
    
16.                 // 将当前元素添加到临时向量中，并递归地搜索其余部分
    
17.                 std::vector<double> temp_vec(vec.begin() + index, vec.begin() + i + 1);
    
18.                 temp_vec.push_back(vec[i]);
    
19.                 if (backtrack(result, temp_vec, i + 1, sum + vec[i], l)) {
    
20.                         return true;
    
21.                 }
    
22.         }
    
23. 
    
24.         return false;
    
25. }
    
26. 
    
27. // 主函数，找到向量a中元素的最大和组合，不超过阈值l
    
28. static std::vector<double> findMaxSumCombination(const std::vector<double>& a, double l) {
    
29.         std::vector<double> result;
    
30.         double current_sum = 0.0;
    
31. 
    
32.         // 调用回溯函数，尝试找到满足条件的组合
    
33.         if (backtrack(result, a, 0, 0.0, l)) {
    
34.                 return result;
    
35.         }
    
36. 
    
37.         return result;
    
38. }
    
39. 
    
40. 
    
41. //std::vector<double> a = {1.0, 2.5, 3.7, 4.2, 5.0, 6.8};
    
42. //double l = 10.0;
    
43. // std::vector<double> c = findMaxSumCombination(a, l);
    
44. // c = {1.0, 3.7,5.0};

复制代码