2

私は部分集合問題の非常に明確な例である問題を抱えています:

「範囲 [-65000,65000] の整数のリストが与えられた場合、合計されたリストのいずれかのサブセットがゼロに等しい場合、関数は true を返します。それ以外の場合は false を返します。」

私が聞きたかったのは、解決策というよりも説明です。

これは、問題の複雑さについて考える前に思いついたインスタンス固有の解決策でした。

  • 配列 A[] を並べ替え、並べ替え中に各要素をカウンター 'extSum' (O(NLogN)) に合計します。
  • ポインター low = A[0] および high = 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 ソリューションを読みましたが、理解したいのは、私が直面している問題の特定のインスタンスについて、この素朴で直感的なソリューションよりもどれだけ優れているかということです。私のアプローチは大幅に改善できることはわかっていますが、時間の複雑さに関しては大きな違いはありません....

説明ありがとうございます

編集:明らかな最適化の 1 つは、並べ替え中に 0 が見つかった場合、関数はすぐに true を返すことです....しかし、配列に 0 がある特定のケースのみです。

4

1 に答える 1

-1

うーん、{0} の方があなたの答えよりも優れていると思います。

while を単に無視して false を返すためです。

于 2011-09-15T16:51:21.017 に答える