問題タブ [dynamic-programming]

companiesから要素を取得し、それらを の要素とペアにするスクリプトに取り組んでいますpeople。目標は、すべてのペア値の合計が最大になるようにペアリングを最適化することです (個々のペアリングの値は事前に計算され、ディクショナリに格納されますctrPairs)。

1対1でペアを組み、1社に1人、1社に1社しか所属せず、社数は人数に等しい。メモ化テーブル ( ) を使用したトップダウン アプローチを使用して、memDict既に解決された領域の再計算を回避しました。

ここで起こっていることの速度を大幅に改善できると信じていますが、どうすればよいかわかりません。私が心配している領域は でマークされてい#slow?ます。アドバイスをいただければ幸いです (スクリプトは n<15 のリストの入力に対しては機能しますが、n > ~15 の場合は非常に遅くなります)。

これは学校に関する質問ですが、宿題ではありません。

私はアルゴリズムのコースを受講しており、現在、Cormen の本、アルゴリズム入門の第 15 章に取り組んでいます。私はこの本のほとんどのアルゴリズムのオンラインの例をたくさん見つけることに成功しており、通常、アルゴリズムがどのように機能するかをよく視覚化する Java アプレットやその他のプログラムを見つけることができます。

その例外は、第 15 章 (動的プログラミング) の Assembly-Line スケジューリングです。

Assembly-Line Scheduling アルゴリズムのさらなる例や視覚化を提供するオンライン リソースを知っている人はいますか?

動的計画法とは

再帰やメモ化などとどう違うのですか?

ウィキペディアの記事を読みましたが、まだよくわかりません。

動的プログラムを取り、それを並列化する方法を議論している良い論文はありますか？

特定のオブジェクトにシングルトン メソッドを追加したいと考えています。オブジェクトのインスタンスメソッドが最初に呼び出されたときに、何らかの作業を行い、同じ名前のオブジェクト (作業を含む) のシングルトンメソッドを作成することを望みます。このオブジェクトに対する後続のすべての呼び出しでは、シングルトン メソッドがインスタンス メソッドをシャドウして呼び出されます。

私はシングルトンメソッドを作成する方法を知っています.私の問題は、ラムダを呼び出すために作成されたシングルトンメソッドが欲しいということです(lこの場合)。def はクロージャーを作成しないため、メソッドが後で呼び出されるときに変数 l (以下のコード) を参照できません (l.call()この例ではコメントアウトされています) 特定のオブジェクトでシングルトン メソッドを作成するときにクロージャーを作成する方法を知りたいです. どんな助けでも大歓迎です。ありがとうございました。

実行すると、次の結果が得られます: (「<」を「#」に変更して、html に表示されるようにしました)

私はすべてのものを代弁します、私はクラスメソッドです

これは Thing オブジェクトによって参照されるインスタンス メソッドです #Thing:0x1d204>

これは Thing オブジェクトによって参照されるインスタンス メソッドです #Thing:0x1d1dc>

これは Thing オブジェクトのシングルトン メソッドです #Thing:0x1d204>

これは Thing オブジェクトの singleton メソッドです #Thing:0x1d1dc>

無向グラフでハミルトン閉路を見つけるための動的計画法アルゴリズムとは何ですか？O(n.2^n)時間計算量のあるアルゴリズムが存在することをどこかで見ました。

元の問題へのリンク

宿題の質問ではありません。誰かがこの問題の本当の解決策を知っているかもしれないと思っただけです。

私は 2004 年にプログラミング コンテストに参加していましたが、次の問題がありました。

n が与えられたとき、n! の桁の合計を求めます。n は 0 ～ 10000 です。制限時間: 1 秒。テストセットごとに最大100個の数字があったと思います。

私のソリューションはかなり高速でしたが、十分に高速ではなかったので、しばらく実行させました。コードで使用できる事前計算された値の配列を作成しました。それはハックでしたが、うまくいきました。

しかし、約10行のコードでこの問題を解決した男がいて、すぐに答えが得られました。ある種の動的計画法か、数論の何かだったと思います。当時私たちは 16 歳だったので、「ロケット科学」であってはなりません。

彼が使用できるアルゴリズムの種類を知っている人はいますか?

編集：質問を明確にしなかった場合は申し訳ありません。^{mquander が言ったように、bugnum を使用せず、単純な Pascal コード、いくつかのループ、O(n 2} ) などを使用する賢い解決策があるはずです。1秒はもはや制約ではありません。

ここで、n > 5 の場合、階乗の桁数の合計が 9 で除算されることがわかりました。また、数字の末尾にあるゼロの数もわかります。それを使えますか？

わかりました、ロシアからのプログラミング コンテストからの別の問題。1 <= N <= 2 000 000 000 の場合、出力 N! mod (N+1)。なんか関係ある？

動的プログラミングの問題に関するいくつかの指針を探しています。この種の問題を解決する方法に関する関連情報が見つかりません。動的計画法を使用して解決する方法を知っている唯一の問題は、2 つのシーケンスがあり、それらのシーケンスの行列を作成する場合です。しかし、それを次の問題に適用する方法がわかりません...

セット A = {7,11,33,71,111} と数値 B がある場合、A のサブセットである C には、合計 B を構築する A の要素が含まれます。

例：

ここで助けてくれてありがとう、この種の問題を解決するときの考え方がわかりません。一般的な方法も見つかりません。遺伝子配列などに関するいくつかの例しかありません。

動的プログラミングを学びたい人のために、扱いやすい例を探しています。ここには、動的プログラミングとは何かについての素晴らしい回答があります。フィボナッチ数列はその良い例ですが、小さすぎて表面をなぞることはできません。私はまだアルゴリズムのクラスを受講していませんが、学ぶのに最適なテーマに見えます。うまくいけば、春のリストに載っていることを願っています。

このアルゴリズムは、私の基本的なプログラミングスキルでは非常に高度であるため、どのように実装できるかわかりません。前の質問のコメントセクションで、これについてアルゴリズムだけを教えてくれた人を悩ませ続けることができないので、これを新しい質問に投稿します。

アルゴリズムを提供してくれたmehrdadにも感謝します。

ここでの問題は、2つの合計行の一部を実装することですが、どうすればそれを実行できますか？そして、このアルゴリズムが選択するすべてのノードにマークを付ける必要があります。これは、trueに設定されたノードクラスの単なる「マークされた」変数です。ノードを選択することも決定したのかわかりませんか？

これまでのコードを含めるように編集します。

これは機能しているようですが、現在残っています。実際にノードを選択済みとしてマークするのですか？私はそれをしましたか？

コードで更新：

提出後、このためのコード全体を投稿します！