Вычислить последовательность целых чисел в векторе

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.

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

Answer 1

Он работает

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

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

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

Вы можете сделать это лучше, используя псевдополиномиальное решение для 0/1 knapsack problem. Идея состоит в том, чтобы создать набор всех возможных сумм до нужного числа 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 

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

Answer 2

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 loop.

Answer 3

У меня этот рабочий код.

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); 
} 

Спасибо, ребята.