Возврат является возможным для этой проблемы.
Он позволяет рекурсивно исследовать все возможности, без необходимости большого объема памяти.
Он останавливается, как только будет найдено оптимальное решение. найдено: sum = X, с точностью до заданного допуска (например, 10 ^ -10 в программе ниже)
Это позволяет реализовать простую процедуру преждевременного отказа :
при данное время, если sum + the sum of all remaining elements выше X, тогда мы можем отказаться от изучения текущего пути, не изучая оставшиеся элементы. Эта процедура оптимизирована путем сортировки входных данных в порядке убывания
Вот код на C ++. Поскольку код довольно прост c, его легко перенести на другой язык.
Эта программа тестирует алгоритм со случайными (равномерными) элементами и отображает количество итераций.
Сложность (то есть количество итераций) действительно зависит от случайных элементов (конечно, ), но также в значительной степени зависит от терпимости, которую мы принимаем. С допуском 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";
}
}