動的プログラミングアルゴリズムn、k問題

StackOverflow https://stackoverflow.com/questions/2245100

質問

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

たとえば、n = 12345とk = 3があるとしましょう。n= 12345とk = 3では、nから3桁を削除することで得られる最大の数は45です（他の変換は12、15、35ですが、45は最大です）。また、Nの数字の順序を変更することはできません（54は解決策ではありません）。別の例は、n = 66621542およびk = 3です。そのため、解は66654になります。

これは動的なプログラミング関連の問題であることを知っており、それを解決することについては考えられません。私はこれを2日間解決する必要があるので、どんな助けも感謝しています。あなたが私のためにこれを解決したくない場合は、あなたはする必要はありませんが、トリックや少なくともいくつかの同様の問題についてもっと読むことができるいくつかの資料を私に向けてください。

前もって感謝します。

役に立ちましたか？

解決

動的なプログラミングの問題を解決するためのトリックは、通常、ソリューションの構造がどのように見えるかを把握すること、そしてそれが具体的に展示されるかどうかを把握することです 最適な下部構造.

この場合、n = 12345とk = 3の最適な解は、解の一部としてn = 12345およびk = 2の最適な解を持っているように思われます。これが当てはまることを自分自身に納得させることができれば、問題の解決策を再帰的に表現できるはずです。次に、メモ化またはボトムアップでこれを実装します。

他のヒント

これは、l =桁数でo（l）で解くことができます。スタックを使用してこれを行うことができるのに、複雑なDP式を使用する理由：

for：66621542スタックにl -k桁以下がある場合にスタックに数字を追加：66621。スタック：

5：5> 2を読んで、スタックから1ポップします。 5> 2、POP 2も。 5：6665を入れてください4：スタックはいっぱいではありません、4：66654を置く2：2 <4を読んでください、何もしません。

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

別の例：12345 l = 5、k = 3 put l -k = 2桁のスタック：12

3、3> 2、POP 2、3> 1、POP 1、PUT 3を読む3。Stack：3 Read 4、4> 3、Pop 3、Put 4：4 Read 5：5> 4、しかしポップできません4、それ以外の場合は、十分な数字が残っていません。だから、5：45を押します。

まあ、動的なプログラミングの問題を解決するには、それを繰り返しのサブソリューションに分解する必要があります。

問題を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（1桁削除されたn、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の辞書的に最大のサブシーケンスを見つけます」。これは本質的にあなたの問題であり、解決策ははるかに簡単です。

これで、別の関数を定義できます b（i、j）, 、長さの最大の辞書編集シーケンスを提供します （i -j）, 、最初のもののみを使用します 私 の数字 n （言い換えれば、削除した 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私 、b（i-1、j-1））

または、場合 j = i それから b（i、j）= b（i-1、j-1）

と b（0、0）= 0

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

動的プログラミングソリューションの2つの最も重要な要素は次のとおりです。

  1. 権利を定義します サブ問題
  2. 定義a 再発関係 サブ問題への答えとより小さなサブ問題への答えの間
  3. 発見 ベースケース, 、答えが他の答えに依存しない最小のサブ問題
  4. を理解する スキャン注文 あなたがサブ問題を解決しなければならない（そうするようにあなたが 初期化されたデータに基づいて再発関係を使用しないでください)

あなたはあなたが正しいサブ問題をいつ定義しているかを知っているでしょう

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

あなたの場合、サブ問題を指定するのは簡単です。これはおそらく宿題なので、私はあなたにそのヒントを与えます あなたは、nがより少ない数字を始めたことを望むかもしれません.

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

左から最初のK + 1桁を考えてみましょう。最大のものを探して、それを見つけて、左の数字を削除します。同じ最大の数の2つが存在する場合は、左端の数を見つけて、その左側の数字を削除します。削除された数字の数を保存します（jに名前を付けます）。

nとk+1 -jと同じように、K+1 -jが1に等しくなるまでこれを行います（うまくいけない場合は、間違えない場合はそうなります）。

あなたが終わらせる数はあなたが探している数になります。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top