問題タブ [dynamic-programming]

あなたが猫のいる高層ビルにいると想像してみてください。猫は低層の窓からの落下に耐えることができますが、高層階から投げられると死にます。最小の試行回数で、猫が生き残ることができる最長の落下をどのように把握できますか？

明らかに、猫が1匹しかない場合は、直線的にしか検索できません。まず1階から猫を投げます。それが生き残った場合は、2番目から投げます。最終的に、f階から投げ出された後、猫は死にます。次に、フロアf-1が最大の安全フロアであることがわかります。

しかし、複数の猫がいる場合はどうなりますか？これで、ある種の対数探索を試すことができます。ビルドに100階があり、2匹の同じ猫がいるとします。最初の猫を50階から投げ出して死んだ場合、50階を直線的に検索するだけで済みます。あなたが最初の試みのために低い階を選ぶならば、あなたはさらに良くすることができます。一度に20階の問題に取り組むことを選択し、最初の致命的な階が＃50であるとしましょう。その場合、最初の猫は20階と40階からの飛行を生き延びてから、60階で死にます。41階から49階までを個別に確認する必要があります。これは合計12回の試行であり、バイナリ除去を使用しようとした場合に必要となる50回よりもはるかに優れています。

一般的に、2匹の猫がいるn階建ての建物にとって、最善の戦略と最悪の場合の複雑さは何ですか？n階とm猫はどうですか？

すべての猫が同等であると仮定します。それらはすべて、特定のウィンドウからの落下で生き残るか、死ぬでしょう。また、すべての試みは独立しています。猫が転倒を生き延びた場合、それは完全に無傷です。

これは宿題ではありませんが、学校の課題で一度解決したことがあるかもしれません。今日頭に浮かんだのは気まぐれな問題で、解決策を覚えていません。誰かがこの問題または解決策のアルゴリズムの名前を知っている場合、ボーナスポイント。

部分和問題の興味深いバリエーションを、職場の友人から教えてもらいました。

サイズ n の正の整数の集合 S と、整数 a および K が与えられた場合、(集合 S の) 部分集合 R のうち、要素 を正確に含み、その合計が K に等しいものはありますか?

彼は、これは時間計算量 O(nka) で実行できると主張していますが、私はこの実行時間を達成する動的計画法のアルゴリズムを思いつくことができませんでした。それはできますか？

私はこのアルゴリズムをPythonで数日間実装しようとしています。私はそれに戻ってきて、ただあきらめてイライラし続けます。何が起こっているのかわかりません。助けを求める人もどこにもいないので、ここに来ました。

PDF警告：http ：//www.cs.uiuc.edu/class/sp08/cs473/Lectures/lec10.pdf

私はそれが明確に説明されているとは思いません、私は確かに理解していません。

何が起こっているのかについての私の理解はこれです：

一連の点（x1、y1）、（x2、y2）..があり、このデータに最適な線をいくつか見つけたいと思います。複数の直線を持つことができ、これらの直線はaとb（y = ax + b）の特定のフォーラムからのものです。

ここで、アルゴリズムは最後（？）から始まり、点p（x_i、y_i）が線分の一部であると想定します。次に、メモには、最適解は'{p1 、.の最適解であると書かれています。。。pi-1}と{pi、。を通る（最良の）線。。。pn}'。これは、私にとっては、ポイントp（x_i、y_i）に移動し、後方に移動して、残りのポイントを通る別の線分を見つけることを意味します。現在、最適なソリューションは、これらの両方の線分です。

次に、私がたどることができない論理的なジャンプが必要で、「最後のポイントpnがp_iで始まるセグメントの一部であると仮定します。Opt（j）が最初のjポイントのコストを示し、e（j、k）点jからkまでの最良の線の誤差、次にOpt（n）= e（i、n）+ C + Opt（i − 1） "

次に、アルゴリズムの擬似コードがありますが、私にはわかりません。ポイントのリストを繰り返し処理して、OPT（n）式を最小化するポイントを見つけたいと理解していますが、私はそれに従いません。それは私を愚かに感じさせています。

この質問はお尻の痛みであり、答えるのは簡単ではないことを私は知っていますが、私はこのアルゴリズムを理解するためのガイダンスを探しています。PDFをお詫びしますが、読者に重要な情報を提供するためのきちんとした方法がありません。

お時間を割いていただき、ありがとうございました。

これは、私が解決しなければならないコンピューター ビジョンの問題のトーンダウン バージョンです。パラメーター n,q が与えられ、n 行 n 列のグリッドの要素に整数 0..(q-1) を割り当てる方法の数を数えなければならない場合を想定して、割り当てごとに以下がすべて真になるようにします。

1. 2 つの隣接 (水平または垂直) が同じ値になることはありません。
2. 位置 (i,j) の値は 0
3. 位置 (k,l) の値は 0

(i,j,k,l) が指定されていないため、出力は (i,j,k,l) の有効な設定ごとに 1 つずつ、上記の評価の配列になります。

ブルート フォース アプローチを以下に示します。目標は、q<=100 および n<=18 で機能する効率的なアルゴリズムを取得することです。

更新 11/11 TopCoderフォーラムでもこれを尋ねましたが、彼らの解決策は私がこれまでに見た中で最も効率的なものです (著者の見積もりから、n=10、任意の q で約 3 時間)

この問題で使用される可能性のあるサブセット合計を生成するプログラムを作成しました。

$1 コインが 3 枚、$2 コインが 2 枚、$5 コインが 3 枚、$10 コインが 1 枚あるとします。これらのコインから $10 を得る方法は 4 つあります。$X1 コインが n1 枚、$X2 コインが n2 枚.... nm $Xm 枚ある場合、これらの限られた数のコインから $X を取得するには、何通りの方法がありますか?

{ X1, X1..... X1, X2, X2.......... X2, ..., ..., ........... .., Xm, Xm... Xm} を実行し、サブセットの合計を実行すると、確かに $X の結果が得られます。しかし、セット {n1, n2, n3.... nm} 、 {X1, X2, X3.... Xm} を使用する方法が見つかりませんでした。ナップザック問題の一種だと友達に言われましたが、どうしてかはわかりません。

これは私が書いたものの部分的なコードです:

もう少し丁寧に説明していただけると助かります。

編集:この質問は、コンピューター サイエンスの stackexchange に適していますが、私の古い質問なので、ここで編集しています。

この問題は、包含除外の原則で解決できます。コインの値は固定されているが、各コインの数はクエリごとに異なる場合に便利です。

way [v]が$x1、$x2、.. $xmで$vを作成する方法であり、それぞれが必要な回数だけ使用されるとします。ここで、 $x1 の n1 個のみを使用している場合、少なくとも( n1 + 1) 個の $x1 (実際には [ v - (n1 + 1)x1 ] の方法) を使用して構成を減算する必要があります。さらに、$x2のn2個だけを使用している場合は、ウェイ[ v - (n2 + 1)x2 ] も減算する必要があります。

ここで、少なくとも ( n1 + 1) $x1および ( n2 + 1) $x2が使用される構成を 2 回減算したため、ウェイを追加する必要があります[ v -(n1 + 1)x1 - (n2 + 1) x2 ] など

特に、

N = すべてのコインができるだけ多く使用される構成のセット、

Ai = 1 <= i <= mの場合、少なくともni + 1 個の$xiが使用される構成のセット

求めている結果 = | ん| - | A1 | - | A2 | .. - | 午前| + | A1とA2 | + | A1とA3 | + ... - | A1とA2とA3 | .....

無制限のコインで構成の数を計算するコードは、実際にはより単純です。

皆さん、

問題に遭遇しました...これは興味深いものでした...それを少し修正しています。

一連の整数 (範囲 0 ～ 500) を指定して、2 つの部分集合をほぼ均等に分割して形成できる和の最小差を見つけます。(整数のカウントが n であるとします。n が偶数の場合、各セットには n/2 要素が必要であり、n が奇数の場合、1 つのセットには (n-1)/2 要素があり、もう 1 つのセットには (n+1)/2 要素があります)

サンプル入力: 1 2 3 4 5 6

最小差 = 1 (サブセットは 1 4 6 および 2 3 5 )

サンプル入力 2 : [ 1 1 1 1 2 2 2 2 ]

最小差 = 0 (サブセットは 1 1 2 2 および 1 1 2 2 )

この問題に対する DP アプローチはありますか。

みんなありがとう...

ラージ...

N 個のコインのリスト、それらの値 (V1、V2、...、VN)、および合計 S が与えられます。合計が S であるコインの最小数を見つけます (1 つのタイプのコインをいくつでも使用できます)。または、合計が S になるような方法でコインを選択することは不可能であると報告します。

動的計画法を理解しようとしていますが、理解していません。与えられた説明が理解できないので、このタスクをプログラムする方法のヒントをいくつか教えていただけませんか? コードはありません。どこから始めるべきかのアイデアだけです。

ありがとう。

私は動的計画法の原理を理解することができず、本当にそれを望んでいます。DPは非常に強力で、次のような問題を解決できます。

数値の差から可能な限り低い合計を取得する

それで、動的計画法とは何かを説明する良い本や記事（できれば実際のコードを使った例を含む）を提案してもらえますか？まず最初に簡単な例が欲しいので、次に進みます。

私は先週このタスクを取得しましたが、問題を解決するための適切なアルゴリズムを見つけることができません。だからここに説明があります：

大きな立方体を小さな立方体に配置せず、硬い立方体を軽い立方体に配置しない場合は、立方体を構築して安定したタワーを構築できます。n個の立方体を持つ可能な限り最高の塔を与えるプログラムを作成します。
入力：
in.txtの最初の行には、キューブの数n（1 = <n = <1000）があります。次のn行は、2つの正の整数、立方体の辺の長さと重さ（どちらも2000以下）で構成されています。辺の長さと重量が同じである類似の立方体はありません
。出力：
可能な限り高い安定したタワーのm番号をout.txtに書き込む必要があります。2行目には、塔の序数mを下から上に書き込む必要があります。塔の高さは、立方体のすべての側面の長さを意味します（立方体の数ではありません）。複数の解決策がある場合は
、入力と出力の例を指定できます。
入力：
5
10 3
20 5
15 6
15 1
10 2 および
出力：
3 215ここにプログラムの制限があります。制限時間：0.2秒 メモリ制限：16 Mb

私がこれを解決するのを手伝ってくれることを願っています。すべての助けのためのthx

これは、ナップザックの問題のバージョンのように思えます。さまざまなサイズの長方形のリストがあり、同じようなサイズを重ねたりグループ化したりせずに、フィールド内に配置したいと考えています。

ナップザックの方向に目を向け始めるのは正しいでしょうか?

ありがとう。