Поскольку задача NP-полная (см. Кормен, "Алгоритмы. Построение и анализ", 3 изд., с. 1147-1151), в общем случае точное решение на сегодняшний день только полный перебор.
В обоснование своего мнения о том, что тут эффективнее применить код Грея (алгоритм взят из "Искусства программирования", т. 4а, с. 338) написал программку с замером времени. Не стал заморачиваться ни с целыми числами (тогда должно быть быстрее...), ни с тем, что в конкретном случае должно быть от 4 до 7 чисел в наборе. Чисто в общем виде. Более того, будем даже считать, что чисел не более 32, чтоб поместиться в 32-битовое число - все равно перебор такого количества уже на грани разумного...
Код приведен далее. Время меряется с помощью QueryPerformanceCounter, т.е. ну очень малые кусочки времени
Понятно, что сравнивать имеет смысл только время полного перебора, т.е. когда решение не найдено. Даже при нашем варианте в 9 чисел время на разбор битов числа примерно в 6-8 раз больше, чем с использованием кода Грея. Для 12 чисел держится уже на уровне 10-11, при 15 - раз в 13-14.
Что касается краткости и прозрачности - сравнивайте сами, насколько 23 (ну, с натяжкой - 25) строк больше 21
Вложенные циклы для конкретной задачи не писал, решая более общую. Кто хочет - допишите, посмотрим, что там...
Код вот:
Код: Выбрать все
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <windows.h>
// Для точного измерения времени...
long long muTime()
{
static class getFreq
{
public:
getFreq() {
LARGE_INTEGER f;
QueryPerformanceFrequency(&f);
freq = f.QuadPart;
}
long long Freq() { return freq; };
private:
long long freq;
} F;
LARGE_INTEGER t;
QueryPerformanceCounter(&t);
return (t.QuadPart * 1000000L)/F.Freq();
}
// Конечно, эффективнее умножить все на 10 и работать с целыми числами,
// но оставим все как есть
double v[] = { 30.5, 772.3, 338.5, 293.2, 532.1,
377.8, 108.2, 236.9, 928.1 };
const int N = sizeof(v)/sizeof(v[0]);
double tgt = 2401.2;
double eps = 0.01; // Чтоб ну совсем по правилам :)
bool version1()
{
// Ну, будем считать, что чисел не слишком много (до 32),
// и что нулевая сумма нас точно не интересует...
for(unsigned long i = (1<<N)-1; i; --i)
{
double sum = 0.0;
for(unsigned long j = i, k = 0; j; j>>=1, ++k)
{
if (j&1) sum += v[k];
}
if (fabs(sum-tgt) < eps)
{
for(unsigned long j = i, k = 0; j; j>>=1, ++k)
{
if (j&1) printf("%.1lf ",v[k]);
}
printf("= %.1lf\n",sum);
return true;
}
}
return false;
}
bool version2()
{
int f[N+1], a[N] = {0};
double sum = 0.0;
for(int i = 0; i <= N; ++i) f[i] = i;
for(int j;;)
{
j = f[0]; f[0] = 0;
if (j == N) break;
f[j] = f[j+1]; f[j+1] = j+1;
if (a[j] = 1 - a[j]) sum += v[j]; else sum -= v[j];
if (fabs(sum-tgt) < eps)
{
for(int i = 0; i < N; ++i)
{
if (a[i]) printf("%.1lf ",v[i]);
}
printf("= %.1lf\n",sum);
return true;
}
}
return false;
}
int main(int argc, const char * argv[])
{
bool res;
long long start = muTime();
res = version1();
long long stop = muTime();
printf("Version 1 = %Ld, result: %d\n",stop-start,res);
start = muTime();
res = version2();
stop = muTime();
printf("Version 2 = %Ld, result: %d\n",stop-start,res);
}
