7

2 つの正の数 N と K を取り、N から K 桁を削除して N を別の数に変換することによって得られる最大の数を計算するアルゴリズム。

たとえば、N=12345 で K=3 の場合、N から 3 桁を削除して得られる最大数は 45 です (他の変換では 12、15、35 になりますが、45 が最大です)。また、N の桁の順序を変更することはできません (したがって、54 は解決策ではありません)。別の例は、N=66621542 で K=3 であるため、解は 66654 になります。

これは動的プログラミングに関連する問題であることはわかっていますが、解決方法がわかりません。これを2日間解決する必要があるので、助けていただければ幸いです。これを解決したくない場合は、解決する必要はありませんが、同様の問題について詳しく読むことができるトリックまたは少なくともいくつかの資料を教えてください.

前もって感謝します。

4

5 に答える 5

6

これは、L = 桁数の O(L) で解くことができます。スタックを使用してこれを行うことができるのに、なぜ複雑な DP 式を使用するのですか?

For: 66621542 スタック上に L - K 桁以下しかない間に、スタックに桁を追加します: 66621. 次に、現在読み取られている桁よりも小さい桁をスタックから削除し、現在の桁をスタック：

5 を読み取ります: 5 > 2、スタックから 1 をポップします。5 > 2、ポップ 2 も。put 5: 6665 read 4: スタックがいっぱいではない、put 4: 66654 read 2: 2 < 4、何もしない。

もう 1 つ条件が必要です。番号に残っている桁数よりも多くのアイテムをスタックからポップしないようにしてください。そうしないと、ソリューションが不完全になります。

別の例: 12345 L = 5、K = 3 L - K = 2 桁をスタックに入れる: 12

3 を読み取り、3 > 2、2 をポップ、3 > 1、1 をポップ、3 をプット。 4 そうしないと、十分な桁数が残りません。5:45 を押します。

于 2010-02-11T15:54:40.120 に答える
5

動的計画法の問題を解決するには、それを繰り返しサブソリューションに分割する必要があります。

問題を A(n, k) として定義するとします。これは、n から k 桁を削除して可能な最大数を返します。

これから単純な再帰アルゴリズムを定義できます。

あなたの例を使用すると、 A(12345, 3) = max { A(2345, 2), A(1345, 2), A(1245, 2), A(1234, 2) }

より一般的には、 A(n, k) = max { A(n から 1 桁を削除、k - 1) }

そして、基本ケースは A(n, 0) = n です。

このアプローチを使用すると、n と k の値をキャッシュするテーブルを作成できます。

int A(int n, int k)
{
  typedef std::pair<int, int> input;
  static std::map<input, int> cache;

  if (k == 0) return n;

  input i(n, k);
  if (cache.find(i) != cache.end())
    return cache[i];

  cache[i] = /* ... as above ... */

  return cache[i];
}

これは簡単な解決策ですが、非常に小さな 1 次元キャッシュで動作するより良い解決策があります。この質問を次のように言い換えることを検討してください:「文字列 n と整数 k が与えられた場合、長さ k の n で辞書編集的に最大のサブシーケンスを見つける」。これが本質的にあなたの問題であり、解決策ははるかに簡単です。

nの最初のi桁のみを使用して(つまり、最初のi桁からj桁を削除して)、長さ(i - j)の最大の辞書式シーケンスを与える別の関数B(i, j)を定義できるようになりました。 nの)。

あなたの例をもう一度使用すると、次のようになります。

B(1, 0) = 1

B(2, 0) = 12

B(3, 0) = 123

B(3, 1) = 23

B(3, 2) = 3

等

少し考えれば、再帰関係を見つけることができます。

B(i, j) = max( 10B(i-1, j) + n i , B(i-1, j-1) )

または、j = iの場合、B(i, j) = B(i-1, j-1)

およびB(0, 0) = 0

そして、上記と非常によく似た方法でコーディングできます。

于 2010-02-11T15:48:35.110 に答える
4

動的計画法の問題を解決する秘訣は、通常、解の構造がどのように見えるか、より具体的には最適な部分構造を示すかどうかを理解することです。

この場合、N=12345 および K=3 の最適解は、解の一部として N=12345 および K=2 の最適解を持つように思えます。これが成り立つと確信できれば、問題の解決策を再帰的に表現できるはずです。次に、メモ化またはボトムアップでこれを実装します。

于 2010-02-11T14:53:50.547 に答える
1

動的計画法ソリューションの最も重要な要素は次の 2 つです。

  1. 適切な部分問題の定義
  2. サブ問題への回答と、より小さなサブ問題への回答との間の再帰関係の定義
  3. 答えが他の答えに依存しない最小のサブ問題である基本ケースを見つける
  4. サブ問題を解決しなければならないスキャン順序を把握する(初期化されていないデータに基づく再帰関係を使用しないようにするため)

次の場合に、適切なサブ問題が定義されていることがわかります。

  • あなたが答えを必要としている問題はそれらの1つです
  • 基本ケースは本当に些細なことです
  • 再発は評価しやすい
  • スキャンの順序は簡単です

あなたの場合、副問題を指定するのは簡単です。これはおそらく宿題なので、最初から N の桁数を減らしてほしいと思うかもしれないというヒントを与えます。

于 2010-02-11T15:40:35.113 に答える
0

これが私が思うことです：

左から最初の k + 1 桁を考えます。一番大きいものを探して見つけ、左側の数字を削除します。同じ最大の数字が 2 つある場合は、一番左の数字を見つけて、その左の数字を削除します。削除された桁数を保存します（ j という名前を付けます）。

新しい数を N として、k+1-j を K として同じことを行います。これを、k+1 -j が 1 になるまで行います (私が間違っていなければ、そうなることを願っています)。

最終的に得られる番号は、探している番号になります。

于 2010-02-11T14:52:35.763 に答える