問題タブ [dynamic-programming]

上記のコードサンプルは、メモ化を使用して、いくつかの入力に基づいて再帰式を計算しますn。同じ式を使用する純粋な再帰関数を記述したため、これがメモ化を使用していることはわかっていますが、これは、の値がはるかに大きい場合にはるかに高速ですn。私はこれまでベクターを使用したことがありませんが、いくつかの調査を行い、ベクターの概念を理解しています。メモ化では、計算された各値が保存されることになっているため、同じ計算を繰り返し実行する代わりに、すでに計算された値を簡単に取得できることを理解しています。

私の質問は、このメモ化はどのように行われ、どのように機能するのかということです。nの値がすでに存在するかどうかを確認する時点で、コードを確認できないようです。また、の目的がわかりませんif(as[n]<=0)。この式は正と負の値を生成する可能性があるため、このチェックが何を探しているのかわかりません。

ありがとう、私はこれがどのように機能するかを理解していると思います。実際、私が思っていたよりも少し単純です。

シーケンス内の値が0になることはないと思います。したがって、nは1から開始する必要があると思うので、これでうまくいくはずです。

しかし、ゼロが私のシーケンスで実行可能な数であった場合、それを解決できる別の方法は何ですか？たとえば、5つが表示されない場合はどうなりますか？ベクトルを5で埋める必要がありますか？

編集：うわー、コードをチェックしてこれを入力しているときに、他にもたくさんの応答がありました。皆さんの助けに感謝します、私は今それを理解していると思います。

現場の問題を解決するために動的計画法の概念を直接適用したのはいつですか? ナップザック問題のでっち上げのインスタンスを解決するためにそれを使用する場合、それをどのように適用できるかが明らかでない場合があります。

部分和の問題に関連する問題があり、その違いによって問題が解決しやすくなるかどうか、つまり妥当な時間で解決できるかどうか疑問に思っています。

値 V、集合サイズ L、数列 [1,N] S が与えられたとき、S のサイズ L のサブセットの合計が V 未満になるのはいくつですか?

これは、次の 3 つの点でサブセット和問題とは異なります。

1. 等しいサブセットの数ではなく、与えられた値よりも小さいサブセットの数を気にします。
2. サブセットのサイズは固定されています。
3. 存在するかどうかだけでなく、合計が V 未満になるセットの数を気にします。

これを解決する合理的に効率的なアルゴリズムはありますか?

編集: 明らかに、これは組み合わせ生成アルゴリズムを使用して O(N choose L) で実行できます。私が本当に興味を持っているのは、それを大幅に高速化する巧妙なハックです。

この三角形には、0 から 4 までの整数の膨大な配列があります。私は Ruby で動的プログラミングを学ぼうとしていますが、次の 3 つの基準を満たす三角形内のパスの数を計算する際に助けが必要です。

1. 70 要素の行のゼロ点の 1 つから開始する必要があります。
2. あなたのパスは、あなたの 1 行真上 (真上に数字がある場合) または 1 行上、左斜め上にある可能性があります。これらのオプションのいずれかが常に利用可能です
3. 最初の行のゼロに到達するまでの経路の合計は、140 になる必要があります。

たとえば、一番下の行の 2 番目のゼロから開始します。1 まで直接移動することも、左斜め 4 まで移動することもできます。1 から真上にある 2 (合計 = 3)、または左斜め上にある 0 (合計 = 1) に移動できます。

更新しました

さらに読んだ後、次の漸化式で解を与えることができます。

これは、パートCを除いて、今では意味をなし始めています。最小値kを決定するにはどうすればよいですか？これは、可能なすべてのk値を反復処理して、（l（k、i）+ dist（pk、pj）の最小結果を格納できることを意味すると思いますか？

はい、確かに私が学校で勉強していた問題です。巡回セールスマン問題のビトニックツアーを研究しています。

とにかく、私が5つの頂点{0,1,2,3,4}を持っているとしましょう。私の最初のステップは、x座標の昇順でこれらを並べ替えることです。そこから、動的計画法でこれがどのように行われるかについて少し混乱しています。

ソートされたノードのリストをスキャンし、両方の部分（初期パスと戻りパス）の最適なパスを維持する必要があることを読んでいます。これらの最適なパスをどのように計算するかについて、私は混乱しています。たとえば、特定のノードを両方に含めることはできないため、最初のパスとリターンパスのどちらに含める必要があるかをどのように知ることができますか（エンドポイントを除く）。動的計画法のフィボナッチを振り返ると、基本的には基本ケースから始めて、前進します。私が求めているのは、バイトニック巡回セールスマン問題をどのように始めればよいのかということだと思います。

フィボナッチ数のようなものの場合、アプローチされる動的計画法は非常に明確です。しかし、私がただ密集しているだけなのか、それとも何なのかはわかりませんが、この問題に頭を悩ませようとするとかなり混乱します。

見てくれてありがとう！

注：私は完全な解決策を探していませんが、少なくともいくつかの良いヒントを探しています。たとえば、これがフィボナッチ数の問題である場合、最初の数個の数値がどのように計算されるかを説明できます。質問を改善する方法も教えてください。

番号のリストがあります。
このリストは、合計の差が最小限になるように、同じサイズの 2 つのリストに分割されます。合計を印刷する必要があります。

場合によっては、次のコード アルゴリズムにエラーがありますか?

これを最適化および/またはPython化するにはどうすればよいですか?

質問はhttp://www.codechef.com/problems/TEAMSEL/からです

「4×1 および 6×1 のレゴ ブロックの列からソリッド パネルを構築するとします。構造強度のために、ブロック間のスペースが隣接する列に並んではいけません。例として、18×3 のパネルが示されています。上の 2 つの行のブロック間のスペースが並んでいるため、以下は受け入れられません。

10×1 パネルを構築するには 2 つの方法、10×2 パネルを構築するには 2 つの方法、18×3 パネルを構築するには 8 つの方法、36×5 パネルを構築するには 7958 通りの方法があります。

64×10 のパネルを構築するには、いくつの方法がありますか? 答えは 64 ビットの符号付き整数に収まります。答えを計算するプログラムを書きなさい。プログラムは非常に速く実行される必要があります。確かに、古いマシンでも 1 分以上かかることはありません。プログラムが計算する値、プログラムがその値を計算するのにかかった時間、実行したマシンの種類をお知らせください。プログラムのソース コードを添付ファイルとして含めます。"

私は最近、プログラミングのパズルを与えられ、それを解こうと頭を悩ませています。私は c++ を使用していくつかのコードを書きましたが、その数が膨大であることはわかっています... 私のプログラムは数時間実行された後、停止することにしました。これに似たパズルを見た人はいますか？数週間経ちましたが、もうこれを提出することはできませんが、正しく解決できなかったことに本当に悩まされています. 使用するアルゴリズムに関する提案はありますか? または、「箱の外」で解決する可能性のある方法かもしれません。私が頼ったのは、4x1および6x1ブロックの可能な「レイヤー」をそれぞれ構築して64x1レイヤーを作成するプログラムを作成することでした。それは約 3300 の異なるレイヤーであることが判明しました。次に、プログラムを実行して、可能なすべての 10 層の高さの壁にそれらを積み重ねて、亀裂が並んでいないようにしました...ご覧のとおり、このソリューションには長い、長い、長い時間がかかります。したがって、時間の制約内でこれを解決するには、明らかにブルートフォースは効果的ではないようです。任意の提案/洞察をいただければ幸いです。

木の最小頂点カバーを取得するための適切なアルゴリズムは何ですか?

入力：

ノードのネイバー。

出力：

頂点の最小数。

全体の順序付けが存在する要素の配列があるとしましょう。バブル ソート距離は、バブル ソートを使用した場合に配列をソートするために必要なスワップの数です。事前に指定された数値以下のバブルソート距離を持つこの配列の可能な順列の数を計算する効率的な (おそらく動的プログラミングを伴う) 方法は何ですか?

問題を単純化する場合は、配列のすべての要素が一意である (関係がない) と想定できます。