Суммируйте последовательность целых чисел в векторе

Question

Суммируйте последовательность целых чисел в векторе

У меня есть функция bool exists(int sum, vector<int>& vec)
Что он делает, так это возвращает ли последовательность чисел в vec это равно sum,

например

Vec = 140 80 90 180 70
sum = 300

Функция возвращает true потому что последовательность 140 90 70 существует и равняется 300.

На данный момент у меня есть код:

bool possible(int sum, vector<int> &vec)
{
do
{
int s = 0;
for (int i = 0; i < vec.size(); i++)
{
s += vec.at(i);
if (s == sum)
{
return true;
}

}
}while(next_permutation(vec.begin(), vec.end()));

return false;
}

Это работает, но занимает слишком много времени, даже если размер вектора равен 20.

Может ли кто-нибудь помочь мне с лучшим подходом?

2

algorithm c++sequences vector

Решение

Другие решения

bool possible(int sum, vector<int> &vec)
{
int s = 0;
for (int i = 0; i<vec.size(); i++)
{
s += vec.at(i);
}

if (s==sum)
return true;
else
return false;

}

Это было бы более эффективно, просто сложив векторные значения и сравнив результаты в конце. В этом случае вы не будете делать никаких вычислений перестановки, и вам не понадобится цикл for внутри цикла do … while.

0

Я получил этот рабочий код.

bool possible(int sum, vector<int &vec)
{
vector<int> previous;
previous.push_back(0);

for(auto i = vec.begin(); i != vec.end(); i++)
{
vector<int> temp(previous);
for(auto j = temp.begin();  j != temp.end(); j++)
*j += *i;
for(auto k = temp.begin(); k != temp.end(); k++)
{
if(*k <= sum)
previous.push_back(*k);
}
}
sort(previous.begin(),previous.end());
return binary_search(previous.begin(),previous.end(),sum);
}

Спасибо, парни.

0

Источник

Accepted Answer

Оно работает

Во-первых, это не совсем работает, если только vec сортируется для начала. Иначе, next_permutation(...) будет производить false без исчерпания всех возможностей, возможно, пропуская перестановку, в которой будет найдено правильное решение.

но занимает слишком много времени, даже если размер вектора равен 20.

Это потому, что это решение O (N!). Обратите внимание, что N! неоправданно высока даже для решения методом грубой силы, потому что порядок, в котором вы делаете дополнения, не имеет значения. Все, что вам нужно, это O (2^N) попробовать все подмножества.

Вы можете добиться большего успеха, используя псевдополиномиальное решение для 0/1 рюкзак проблема. Идея состоит в том, чтобы создать набор всех возможных сумм с точностью до требуемого числа N. Начните набор с одного числа, ноль. На каждой итерации создается еще один набор, содержащий все элементы набора из предыдущей итерации, плюс набор, полученный путем добавления числа из вашего списка к каждой из предыдущих сумм, ограничивая значения целевым числом (т. Е. 300):

{ 0 }
{ 0, 140 } -- Added 0+140
{ 0, 80, 140, 220 } -- Added 0+80, 140+80
{ 0, 80, 90, 140, 170, 220, 230 } -- Added 0+90, 80+90, 140+90; 220+90 > 300, so it is not added
... // And so on

В конце этого процесса у вас будут все возможные суммы в наборе. Теперь все, что вам нужно сделать, это проверить, присутствует ли ваш целевой номер среди предметов в наборе.

4