findMaxSumCombination Code error

[1127204185]

std::vector<double> a = {1.0, 2.5, 3.7}
std::vector<double> b = {4.2, 5.0, 6.8}，
double l = 10

result  std::vector<double> c = {1.0, 5.0, 3.7} 
std::accumulate(c.begin(), c.end(), 0.0) <= l

Method 1
void backtrack(const std::vector<double>& a, const std::vector<double>& b, std::vector<double>& c, int index, double sum, double threshold, double& maxSum) {
    if (sum > threshold) {
        return;  // 当前组合的和已经大于阈值，剪枝
    }
   
    if (sum > maxSum) {
        maxSum = sum;  // 更新最大和
    }
   
    if (index >= a.size() && index >= b.size()) {
        return;  // 已经遍历完所有元素，结束递归
    }
   
    if (index < a.size()) {
        c.push_back(a[index]);  // 将a中的元素加入组合c
        backtrack(a, b, c, index + 1, sum + a[index], threshold, maxSum);
        c.pop_back();  // 回溯，将a中的元素移出组合c
    }
   
    if (index < b.size()) {
        c.push_back(b[index]);  // 将b中的元素加入组合c
        backtrack(a, b, c, index + 1, sum + b[index], threshold, maxSum);
        c.pop_back();  // 回溯，将b中的元素移出组合c
    }
}

std::vector<double> findMaxSumCombination(const std::vector<double>& a, const std::vector<double>& b, double threshold) {
    std::vector<double> c;
    double maxSum = 0.0;
    backtrack(a, b, c, 0, 0.0, threshold, maxSum);
    return c;
}

Method 2

// 回溯函数，寻找给定向量vec中元素的最大和组合，不超过阈值l
static bool backtrack(std::vector<double>& result, const std::vector<double>& vec, size_t index, double sum, double l) {
        // 基本情况：如果当前和等于阈值，说明找到了一个有效的组合
        if (sum == l) {
                result = vec;
                return true;
        }

        // 遍历向量中剩余的元素
        for (size_t i = index; i < vec.size(); ++i) {
                // 跳过那些加上当前和会超过阈值的元素
                if (sum + vec[i] > l) {
                        continue;
                }

                // 将当前元素添加到临时向量中，并递归地搜索其余部分
                std::vector<double> temp_vec(vec.begin() + index, vec.begin() + i + 1);
                temp_vec.push_back(vec[i]);
                if (backtrack(result, temp_vec, i + 1, sum + vec[i], l)) {
                        return true;
                }
        }

        return false;
}

// 主函数，找到向量a中元素的最大和组合，不超过阈值l
static std::vector<double> findMaxSumCombination(const std::vector<double>& a, double l) {
        std::vector<double> result;
        double current_sum = 0.0;

        // 调用回溯函数，尝试找到满足条件的组合
        if (backtrack(result, a, 0, 0.0, l)) {
                return result;
        }

        return result;
}


//std::vector<double> a = {1.0, 2.5, 3.7, 4.2, 5.0, 6.8};
//double l = 10.0;
// std::vector<double> c = findMaxSumCombination(a, l);
// c = {1.0, 3.7,5.0};

[tbrammer]

You didn't write what you code is supposed to do. But it doesn't seem to be related to ObjectARX. 

It looks like it shall search for a combination of numbers from a and b that have the biggest possible sum <= 10.

Is there any boundary condition how many elements must/may be used from a and b? If not it would be easier to use only one vector with all numbers.

[1127204185]

Sorry, it's a C++issue。
It's just a random combination, finding the biggest possible sum <= 10。
Try two methods and see which one is faster?

[tbrammer]

If I understand it correctly then this is exactly what you are looking for 😁. 

Just put all numbers into one single std::vector and use

ValSum valsum(valArr, 10.0);

 It should be the fastest possible solution.

[1127204185]

Thank you very much!  

[1127204185]

map<double, int> _Map;
_Map.insert(pair<double,unsigned>(1.2,2));
_Map.insert(pair<double,unsigned>(2.3,2));
_Map.insert(pair<double,unsigned>(5.6,6));
_Map.insert(pair<double,unsigned>(6.7,4));
_Map.insert(pair<double,unsigned>(8.9,6));

double l =60.4；

According to the code, from large to small
1.2+1.2+2.3+2.3+5.6+5.6+5.6+5.6+5.6+5.6+6.6+6.7+6.7=54
1.2+1.2+2.3+2.3+5.6+5.6+5.6+5.6+5.6+5.6+6.6+6.7+6.7+6.7+6.7=60.7
Maximum quantity 12
8.9+8.9+8.9+8.9+8.9+8.9+8.9+6.9+6.7=60.1
8.9+8.9+8.9+8.9+8.9+8.9+6.9+6.7+6.7=66.8
Minimum quantity 7
So only considering quantity n>=7&&n<=12

Can you optimize it to increase speed！

[1127204185]

map<double, int> _Map;
_Map.insert(pair<double,unsigned>(5.6,600));
_Map.insert(pair<double,unsigned>(6.7,400 ));
_Map.insert(pair<double,unsigned>(8.9,600 ));
_Map.insert(pair<double,unsigned>(12.3,200 ));
_Map.insert(pair<double,unsigned>(15.6,600 ));
_Map.insert(pair<double,unsigned>(16.7,400 ));
_Map.insert(pair<double,unsigned>(18.9,600));
_Map.insert(pair<double,unsigned>(21.2,200));
_Map.insert(pair<double,unsigned>(25.6,600));
_Map.insert(pair<double,unsigned>(26.7,400 ));
_Map.insert(pair<double,unsigned>(28.9,600 ));

double l =60.4；

result： 28.9+28.9

 5.6+5.6+12.3+12.3+12.3+12.3 =60.4 

5.6+5.6+5.6+5.6+5.6+5.6+5.6+21.2 =60.4

[tbrammer · Accepted solution]

Try this.

[1127204185]

Thank you very much for your help