13

例: 配列: 4,3,0,1,5 {すべての数字が >=0 であると仮定します。また、配列の各要素は数字に対応します。つまり、配列の各要素は 0 から 9 の間です。 }

上記の配列では、最大数は次のとおりです: 5430 {配列の数字 5、4、3、および 0 を使用}

私のアプローチ:

3 で割り切れるには、桁の合計が 3 で割り切れる必要があります。したがって、

  1. ステップ-1: 配列からすべてのゼロを削除します。
  2. ステップ-2: これらのゼロは最後に来ます。{合計には影響しないため、最大数を見つける必要があります}
  3. ステップ-3: 桁数が MAXIMUM で、桁の合計が MAXIMUM で、合計が 3 で割り切れる配列の要素のサブセット (ゼロを除く) を見つけます。
  4. STEP-4: 必要な数字は、上記の見つかったセットの数字を降順に並べたものです。

したがって、主なステップはSTEP-3です。つまり、合計がMAXで3で割り切れるMAXIMUM可能な要素数を含むサブセットを見つける方法です。

ステップ 3 は、すべての要素を取り、合計が 3 で割り切れるまでセット内の最小の要素を削除し続けるという GREEDY CHOICE によって実行できるのではないかと考えていました。

しかし、この貪欲な選択が機能するとは確信していません。

私のアプローチが正しいかどうか教えてください。もしそうなら、Step-3のやり方を教えてください。

また、他の可能な/効率的なアルゴリズムを提案してください。

4

6 に答える 6

17

観察： 3で割り切れる数を得ることができる場合、最適な解を維持するために、最大2つの数を削除する必要があります。

簡単なO(n^2)解決策は、1つの番号を削除するすべての可能性をチェックし、有効なものがない場合は、すべてのペアをチェックすることです（O(n^2)それらがあります）。

編集：
O(n)解決策：3つのバケットを作成します- bucket1、、。それぞれが数値のモジュラス3値を示します。次のアルゴリズムでは無視します。bucket2bucket0bucket0

配列の合計を。としますsum。

If sum % 3 ==0: we are done.
else if sum % 3 == 1:
  if there is a number in bucket1 - chose the minimal
  else: take 2 minimals from bucket 2
else if sum % 3 == 2
  if there is a number in bucket2 - chose the minimal
  else: take 2 minimals from bucket1

注：スペースを確保するために、実際にはバケットは必要ありません。これらのバケットから実際に使用した数は、とO(1)からの2つの最小値のみです。bucket1bucket2

例：

arr = { 3, 4, 0, 1, 5 }
bucket0 = {3,0} ; bucket1 = {4,1} bucket2 = { 5 }
sum = 13 ; sum %3 = 1
bucket1 is not empty - chose minimal from it (1), and remove it from the array.
result array = { 3, 4, 0, 5 } 
proceed to STEP 4 "as planned"
于 2012-09-19T11:24:55.987 に答える
5

貪欲な選択は絶対にうまくいきません: set を考えてみて{5, 2, 1}ください。1最初は削除しますが、2.

モジュロ 3 の配列の合計を計算する必要があると思います。これは 0 (完了)、1、または 2 のいずれかです。次に、モジュロ 3 の合計が 1 または 2 である最小サブセットを削除しようとしています。

それはかなり簡単だと思うので、動的プログラミングは実際には必要ありません。可能であれば、そのモジュラスで 1 つの数値を削除して実行します。そうでない場合は、他のモジュラスで 2 つの数値を削除して実行します。削除する数がわかったら、可能な限り小さいものを選択します。3 つの数字を削除する必要はありません。

特別に処理する必要はありませんが、処理する0場合は、手順 3 で検討中のセットから 0、3、6、9 をすべて一時的に削除すると、さらにそのセットを減らすことができます。

すべてをまとめると、おそらく次のようになります。

  • 数字を降順に並べ替えます。
  • モジュラスを計算します。0 の場合は終了です。
  • 最後から始めて、そのモジュラスを持つ数字を削除してみてください。成功したら終了です。
  • 最後から始めて、モジュラスが負の 2 桁を削除します。これは常に成功するので、これで終了です。
  • 空の配列が残る可能性があり (たとえば、入力が の1, 1場合)、その場合、問題は発生しませんでした。それ以外の場合、配列には結果の数字が含まれます。

O(n)ステップ1でカウントソートを実行すると、時間の複雑さが提供されます。値が数字であるため、これは確かに可能です。

于 2012-09-19T11:31:08.763 に答える
1

まず、この問題は、選択された要素の数を最大化して、それらの合計が3で割り切れるようにすることになります。

些細なこと：3（0,3,6,9）で割り切れるすべての数値を選択します。

Le aは1を余りとして残す要素であり、bは2を余りとして残す要素です。（| a |-| b |）％3が0の場合、aとbの両方からすべての要素を選択します。（| a |-| b |）％3が1の場合、bからすべての要素を選択し、aから| a|-1個の最大数を選択します。余りが2の場合は、aからすべての数値を選択し、bから| b|-1の最大の数値を選択します。

すべての番号を取得したら、逆の順序で並べ替えて連結します。それがあなたの答えです。

最終的に、nが要素の数である場合、このアルゴリズムは少なくともn-1桁の長さの数を返します（コーナーケースを除く。以下を参照）。

注：コーナーケースに注意してください（つまり、| a |=0または|b| = 0など）。（-1）％3 = 2および（-2）％3=1。

mがアルファベットのサイズで、nが要素の数である場合、このアルゴリズムはO（m + n）です。

于 2012-09-19T12:03:26.423 に答える
1

これについてあなたはどう思いますか：

最初に配列要素を値でソートします

sum up all numbers
- if sum's remainder after division by 3 is equal to 0, just return the sorted
  array
- otherwise
    - if sum of remainders after division by 3 of all the numbers is smaller
      than the remainder of their sum, there is no solution
    - otherwise
        - if it's equal to 1, try to return the smallest number with remainder
          equal to 1, or if no such, try two smallest with remainder equal to 2,
          if no such two (I suppose it can happen), there's no solution
        - if it's equal to 2, try to return the smallest number with remainder
          equal to 2, or if no such, try two smallest with remainder equal to 1,
          if no such two, there's no solution

最初に配列要素を 3 で割った剰余で昇順に並べ替え、次に等しい剰余の各サブセットを値で降順に並べ替えます。

于 2012-09-19T11:41:32.510 に答える
0

異なる値は 10 個しかないため、データの並べ替えは不要です。n桁が与えられた場合、O（n）のゼロ、1、2などの数を数えるだけです。すべての桁の合計を計算し、モジュロ 3 の剰余が 0、1、または 2 であるかどうかを確認します。

余りが 1 の場合: 次のうち可能な最初のものを削除します (これらのうちの 1 つが可能であることが保証されています): 1、4、7、2+2、2+5、5+5、2+8、5+ 8、8+8。

剰余が 2 の場合: 可能な次の最初のものを削除します (これらのうちの 1 つが可能であることが保証されています): 2、5、8、1+1、1+4、4+4、1+7、4+ 7、7+7。

桁が残っていない場合、問題は解決できません。それ以外の場合は、9、8、7 などを残りの数だけ連結して解を作成します。

（n桁のソートにはO（n log n）が必要です。もちろん、各桁の発生頻度を数えてソートし、これらの数値に従ってソート結果を生成しない限り）。

于 2014-06-08T23:09:15.097 に答える
0

アミットの答えには、小さなものが欠けています。

バケット 1 が空ではなく、巨大な値を持っている場合、79 と 97 があり、b2 も空ではなく、その 2 つの最小値が 2 と 5 であるとします。この場合、すべての桁の合計のモジュラスが1 の場合、最大の連結数を取得するには、バケット 1 の最小値ではなく、バケット 2 から 2 と 5 を削除することを選択する必要があります。

テストケース: 8 2 3 5 78 79

Amits と Steve の提案する方法に従うと、最大数は 878532 になりますが、この配列で 3 で割り切れる最大数は 879783 です。

解決策は、適切なバケットの最小最小値を他のバケットの両方の最小値の連結と比較し、小さい方を削除することです。

于 2015-06-30T08:18:03.250 に答える