给定一组正整数和值X，找到一个其和>=X的子集S，使得sum(S)是这类已有子集的所有和中的最低值

Question

给定一组正整数和值X，找到一个其和>=X的子集S，使得sum(S)是这类已有子集所有和中的最低值。

Answer 1

回溯是这个问题的一种可能。

它允许递归地检查所有可能性，而不需要大量内存。

一旦找到最优解，它就会停止:sum=x，直到给定的容差（例如下面程序中的10^-10)

复杂度（即迭代次数）确实随随机元素而变化（当然），但也很大程度上取决于我们接受的容忍度。在容差为10^-10和大小为n=100的情况下，复杂度通常是可以接受的。如果容差较小，情况就不再是这样了。

通过n=100和五次运行，我得到了迭代次数：6102,3672,8479,2235,12926。然而，很明显，并不保证在所有情况下都有良好的性能。对于n=100，候选（子集）的数量是巨大的。

//  Find min sum greater than a given number X

#include    <iostream>
#include    <iomanip>
#include    <vector>
#include    <algorithm>
#include    <tuple>
#include    <cstdlib>
#include    <cmath>
#include    <ctime>

std::tuple<double, std::vector<double>> min_sum_greater(std::vector<double> &a, double X) {
    int n = a.size();
    std::vector<bool> parti (n, false);     // current partition studies
    std::vector<bool> parti_opt (n, false);  // optimal partition
    std::vector<double> sum_back (n, 0);   // sum of remaining elements

    //std::cout << "n = " << n << " \tX = " << X << "\n";
    std::sort(a.begin(), a.end(), std::greater<double>());

    sum_back[n-1] = a[n-1];
    for (int i = n-2; i >= 0; --i) {
        sum_back[i] = sum_back[i+1] + a[i];
    }
    double sum = 0.0;     // current sum

    int i = 0;          // index of the element being examined
    double best_sum = sum_back[0] + 1.0;
    bool up_down = true;
    double eps = 1.0e-10;       // error tolerance
    long long cpt = 0;      // to check the number of iterations

    while (true) {          // UP
        //std::cout << "Start of while loop: i = " << i << "\n";
        cpt++;
        if (up_down) {
            bool abandon = (sum + sum_back[i] < X - eps) || (sum > best_sum);
            if (abandon) {  //premature abandon
                parti[i] = false;
                up_down = false;
                i--;
                continue;
            }

            parti[i] = true;
            sum += a[i];
            //std::cout << "UP, i = " << i << " \tsum = " << sum << "\n";

            if (fabs(sum - X) < eps) {
                best_sum = sum;
                parti_opt = parti;
                break;
            }

            if (sum >= X) {
                if (sum < best_sum) {
                    best_sum = sum;
                    parti_opt = parti;
                    //std::cout << "i = " << i << " \tbest sum = " << best_sum << "\n";
                }
                parti[i] = false;
                sum -= a[i];
            }

            if (i == (n-1)) {           // leaf
                up_down = false;
                i--;
                continue;
            }
            i++;        

        } else {            // DOWN
            if (i < 0) break;
            if (parti[i]) {
                sum -= a[i];
                parti[i] = false;
                i++;
                up_down = true;
            } else {
                i--;
                up_down = false;
            }
        }
    }
    std::vector<double> answer;
    for (int i = 0; i < n; ++i) {
        if (parti_opt[i]) answer.push_back (a[i]);
    }
    std::cout << "number of iterations = " << cpt << " for n = " << n << "\n";
    return std::make_tuple (best_sum, answer);
}

int main () {
    //std::vector<double> a = {5, 6, 2, 10, 2, 3, 4, 13, 17, 38, 42};
    double X = 33.5;

    srand (time(NULL));
    int n = 100;
    double vmax = 100;
    X = vmax * n / 4;
    std::vector<double> a (n);
    for (int i = 0; i < n; ++i) {
        a[i] = vmax * double(rand())/RAND_MAX;
    }

    double sum;
    std::vector<double> y;
    std::tie (sum, y) = min_sum_greater (a, X);

    std::cout << std::setprecision(15) << "sum = " << sum << "\n";

    if (n < 20) {
        std::cout << "set: ";
        for (auto val: y) {
            std::cout << val << " ";
        }
        std::cout << "\n";
    }

}