1

n 桁の数字と数字のリストがあり、そこから任意の数字を何度でも使用できます。

リストから数値を取得して、合計の最後の n 桁が n 桁の数値になるように合計を生成できることをどのように知ることができますか?

注: 合計には初期値があり、ゼロではありません。

編集- 解決策が存在する場合、指定された番号として最後の 4 桁を持つような番号を取得するために追加される番号の最小数を見つける必要があります。それはDP（最小コイン変更問題）で簡単に解決できます。

たとえば、n=4 の場合、

Given number  = 1212
Initial value = 5234
List = [1023, 101, 1]
A solution exists: 21212 = 5234 + 1023*15 + 101*6 + 1*27
4

2 に答える 2

1

反例を見つけるのは簡単です (コメントを参照)。

さて、解決策として、動的プログラミングのアプローチを次に示します。

すべての算術演算はモジュロ 10^n です。0 から 10^n-1 の範囲の値ごとに、それが見つかったかどうかのフラグが必要であり、要素を処理するためのキューが必要です。

  1. 初期値を処理対象リストにプッシュします。
  2. 処理対象リストから要素を取得します。空なら終了。解決策はありません。
  3. この数に各数を別々に追加してみてください。すでに見つかっている場合は、何もする必要はありません。合計が見つかった場合は、完了です。解決策があります。そうでない場合は、見つかったものとしてマークし、キューにプッシュします。
  4. 後藤2

数値に到達した方法を保存すると、実際の解を再構築できます。初期値に達するまで、合計から戻る必要があります。

于 2013-06-07T02:55:01.307 に答える