7

私はコーディングコンテストでこの質問に出くわしました-

正の整数の配列が与えられ、必要なときにいつでも任意の整数の符号を変更できます。この配列の最小合計を計算するプログラムを作成します。この合計は>=0である必要があります。例：Array = {1,2,4,5}次に、1と5の符号を変更するとsum = 0 {-1,2,4、-5}

この問題に対する私の解決策は、配列を並べ替えて、すべてのメンバーの合計を見つけることでした。次に、合計から2 *（並べ替えられた配列値）を繰り返し減らします。最大数から始めて、合計が0になるか、負になるまで続けます。

しかし、私の解決策は間違っています。12,13,14,15,16,50を取る。私のコードは50から-50に変更され、停止します（つまり、最小合計= 20）。しかし、答えは12、-13、-14、-15、-16,50（最小合計= 4）である必要があります

4

4 に答える 4

9

この問題はナップサック問題に変更できます

この問題を考えてみましょう:

n 個の整数が与えられ、明らかに、これらの数の合計を計算できます。S と仮定します。

それらから一連の数値を選択する必要があり、これらの選択した数値を合計して S/2 にできるだけ近づけることを目指します。

これは、ナップサック問題に非常によく似た DP アルゴリズムを使用して実行できます。

今すぐできますか？:)

この投稿は単なるヒントです。さらにサポートが必要な場合は、詳細をお知らせします

于 2013-01-11T08:06:14.747 に答える
4

ナップサックについて何かを言って、私は他の答えにイライラしました。

ナップサックとは、ターゲットSと重みのリストがあり、その合計が になるサブセットをA探していることを意味します。AS

私には、2 台のマシンがあり、makespan が最小になるようにすべてのジョブをそれらに割り当てる必要がある makespan スケジューリングのように見えます。

したがって、2 つのスタックとして考えることができ、それらの高さの差を最小限に抑えようとします。

3/2 近似アルゴリズムは次のとおりです。

  • リストを並べ替えます (最大から最小)
  • オブジェクトごとに、最も低い高さのスタックに配置します

小さい方のスタック上のすべてのオブジェクトの符号を負にして数値を合計することで、概算値を取得します。(つまり、両方のスタックの絶対差を計算します)

最小メイクスパン スケジューリングを検索すると、 PTASと、リストの長さで指数時間を必要とする正確なアルゴリズムを見つけることができます。

于 2014-08-12T05:41:21.943 に答える
2

上記のコードを書きましたが、動作しているようです。

間違っていたら訂正してください！

public int minimumSum(int[] array)
{
      int counter1, counter2, minimumSum;
      int n = array.length;
      counter1 = array[n-1];
      counter2 = array[n-2];
      // It is assumed that the array is sorted.
      int i = n-3;
      while(i>=0)
      {
          if(counter1 > counter2)
          { 
              counter2 = counter2 + array[i];
          }
          else
          {
              counter1 = counter1 + array[i];
          }
          i--;
      }
      if(counter1 > counter2)
      {
          minimumSum = counter1 - counter2;
      }
      else
          minimumSum = counter2 - counter1;
      return minimumSum ;
}
于 2014-08-12T03:19:51.747 に答える