問題タブ [greedy]

JAVA を使用して、指定された文字列で次のグループをキャプチャするための正規表現は何ですか:

最初の単語にはコンマも含めることができるという制約があります。次の正規表現があります。

しかし、基本的には最後の 3 つのコンマのみを一致させたいと考えています。

私の質問は、開始時刻と終了時刻が記載されたアクティビティのリストが与えられた後、実行できる最大のアクティビティを見つけなければならないということです。質問はかなり一般的で、貪欲なアプローチを適用しましたが、コードでランタイムセグメンテーション エラーが発生しているため、以下に投稿しています。

よろしくお願いします!! 事前にサンクス!!

以下は、CSアルゴリズムの講師によるクラスカルの最小スパニングツリーアルゴリズムの擬似コードです。MSTアルゴリズムが非決定論的であるかどうかを知りたいと思いました。同じ重みを持つ2つのエッジが与えられた場合、Tに追加するときにどちらのエッジもサイクルを形成しなかった場合、アルゴリズムはどのようにそれらを決定しますか。確かにランダムである場合、Tに追加された正確なエッジの結果を判断できません。

ありがとう！

無向の重み付きグラフG=（V、E）が与えられます。各頂点は都市を表し、aとbに接続されたエッジの重みは、都市aと都市bの間の高速ルートの構築を完了するのにかかる年数です。グラフ内の任意の2つの都市間を移動できるようになるまでの最短年数を見つけるアルゴリズムを説明してください。ルートは同時に構築されているため、3つの都市a、b、cがあり、aとbの間に重み1のエッジがあり、bとcの間に重み2のエッジがある場合、出力は2になります。

問題

N 個の実数 A = {x_1, x_2, ..., x_N}のセットがあるとします。

目標は、このセットをA_1、A_2、...、A_Lサブセットに分割し、 sum( A_i ) <= Tの制限とこの項を最小化することです。

コスト := sum( abs( sum(A_i) - T ) )

ここで、sum(A_i)はA_iの数値の合計を表し、Tは特定のしきい値です。

非進化的最適アルゴリズムを探しています。

更新: x_iは正の実数であり、T ( 0 < x_i <= T ) 以下です。

更新 2:コスト関数が修正されました。

がんばれ、貪欲アルゴリズム！

簡単なアイデアは、貪欲なアプローチを使用して問題を解決することです。擬似コードは次のとおりです。

問題は、このソリューションが最適ではないことです。たとえば、最初のサブセットA_1に 2 つの最大数x1とx2を入れないほうがよい場合があります。これは、そのセットに追加して作成できる * x_i * が他にないためです。その合計はTに近くなります。一方、x1とx2を別々のセットに入れておけば、より良い解 ( Cost値が小さい解) を見つけることができます。

可能な解決策

最適な解を見つけることができるバックトラッキングアルゴリズムを使用することも考えましたが、この問題の複雑さは高いと思います。

ウィキペディアでビン パッキング問題(NP-hard [ため息...] ) やカッティング ストックの問題などの記事を読んだことがありますが、どうやら私の問題はこの標準的な問題と非常によく似ていますが、どれが私のケースに一致するかわかりません。

長さの文字列があり1 <= |S| <= 100、K (1 <= K <= 10)

この文字列にはdigits < Kと 疑問符が含まれています。これらの疑問符を に置き換えたいのですがdigits < K、隣り合う 2 つの数字が同じではありません。文字列は円形なので、次のようにすることはできません:1?1または11?.

結果の文字列は、辞書編集的に最小のものでなければなりません。

入力と出力の例

私は貪欲なアプローチを試みましたが、いくつかの未知のテストケースでは失敗します。dp アプローチが必要だと思いますが、状態を把握できず、純粋な再帰コードは間に合いません。

dp アプローチ、または貪欲に失敗するトリッキーなテスト ケースの助けはありますか?

ありがとう、

アルゴリズムに関する簡単な質問があります。助けていただければ幸いです。

2 次元の点がいくつかあります。それらには正の重みが関連付けられています（サンプル問題が添付されています）。重みを最大化し、選択した 2 つの点が互いに重ならないサブセットを選択したい (たとえば、添付ファイルでは、A と C は同じ行にあり、同じ方法で選択できないため、両方を選択することはできません) A と B は同じ列にあるため、両方を選択することはできません。)貪欲な (または動的な) アプローチがあれば、使用できます。重複しない間隔選択アルゴリズムを認識していますが、ここでは使用できません。問題が 2 次元であるためです。

任意の参照またはメモをいただければ幸いです。

よろしく

添付ファイル: 問題の簡単なサンプル:

最適化問題を解決できるため、貪欲なアプローチよりもDPアプローチに偏っている人がいます。どちらが好ましいと思いますか？私は私の仲間と議論するために好ましい技術を支持して議論を集める必要があります。笑。わかりました。DPは、最適な部分構造を持つ問題を解決するために使用され、最適性の原則が適用されます。しかし、DPが欲張りアプローチよりも優れているだけで十分ですか？

ほとんどの場合、混乱を招く事実は、問題を解決するために徹底的な検索 (動的プログラミングまたはバック トラッキングまたはブルート フォース) を使用するか、貪欲なアプローチを使用するかです。

私は貪欲を使用して可能な限り最善の解決策を決定することについて話しているのではなく、貪欲なアルゴリズムを使用して「解決策」を見つけることについて話しているのです。問題が貪欲なアプローチで解決できるかどうかを検証できる標準的な方法をいくつか取得しようとしています。最適部分構造と同様に、動的計画法の暗記。そして、特定の問題に関連していません。

貪欲なアプローチが常に最良の解決策を生み出すかどうかを判断するために私ができる誘導の証拠はありますか?

根付きツリーとしてモデル化できる論理回路が与えられます。葉は主要な入力であり、内部ノードはゲートであり、根は回路の単一の出力です。各ゲートは、高または低電源電圧で駆動できます。低い電源電圧で駆動されるゲートは、消費電力が少なくなりますが、出力信号が弱くなります。回路の信頼性を確保しながら、電力を最小限に抑える必要があります。信頼性を確保するために、低電源電圧で電力を供給されるゲートで、低電源電圧で電力を供給される別のゲートを駆動しないでください。すべてのゲートは、低電源電圧に接続すると 1 ナノワット、高電源電圧に接続すると 2 ナノワットを消費します。

論理回路を入力として受け取り、信頼性の高い動作を確保しながら消費電力を最小限に抑えるために、各ゲートの供給電圧を選択する効率的なアルゴリズムを設計します。

この質問では、貪欲または動的を使用して解決できると思います。しかし、私はどこからこの問題を考え始めることができるのか混乱しています。助けてください。