Экземпляр проблемы суммы подмножеств - PullRequest
Новая
       19

Экземпляр проблемы суммы подмножеств

2 голосов
/ 15 сентября 2011

У меня есть проблема, которая является довольно ясным примером проблемы суммы подмножеств:

", учитывая список целых чисел в диапазоне [-65000,65000], функция возвращает значение true, если любое подмножество суммированного списка равно нулю. В противном случае - false."

То, что я хотел спросить, - это скорее объяснение, чем решение.

Это было решение для конкретного экземпляра, которое я придумал, прежде чем думать о сложности проблемы.

  • Сортировать массив A [] и, при сортировке, суммировать каждый элемент в счетчике 'extSum' (O (NLogN)) *
  • Определить для указателей низкий = A [0] и высокий = A [n-1]
  • Вот решающий код: 
  • while(A[low]<0){
  sum = extSum;
  if(extSum>0){
    while(sum - A[high] < sum){
        tmp = sum - A[high];
        if(tmp==0) return true;
        else if(tmp > 0){
            sum = tmp;
            high--;
        }
        else{
            high--;
        }
    }
    extSum -= A[low];
    low++;
    high = n - 1;
  }
  else{
    /* Symmetric code: switch low, high and the operation > and < */
  }
}
return false;

Прежде всего, правильно ли это решение? Я сделал несколько тестов, но я не уверен ... это выглядит слишком просто ...
Разве не сложность по времени этого кода O (n ^ 2)?

Я уже читал различные решения DP, и мне хотелось бы понять, насколько лучше для этого конкретного наивного и интуитивного решения они являются для конкретного случая проблемы, с которой я сталкиваюсь. Я знаю, что мой подход может быть значительно улучшен, но ничего, что могло бы иметь большое значение, когда речь заходит о сложности времени ...

Спасибо за разъяснения

РЕДАКТИРОВАТЬ: Одна очевидная оптимизация состояла бы в том, что при сортировке, если найден 0, функция немедленно возвращает true .... но это только для конкретного случая, в котором в 0 есть 0 массив.

1 Ответ

0 голосов
/ 15 сентября 2011

Хм, я думаю, что {0} побьет ваш ответ.

Потому что он просто проигнорирует while и вернет false.

...