問題タブ [greedy]

範囲を検証する必要があります。入力は次の形式です。

次の正規表現を使用しています。

ユーザーが入力"anydate between 20100101 ~~ 20100101 and test1"すると失敗し、までキャプチャしtest1ます。

正規表現の貪欲さを減らし、キャプチャまでのみにする方法は20100101?

後述のアルゴリズムの問​​題で問題があります。

ある港に 3 車線のフェリーがあり、その前に N 台の車が並んでいます。それぞれにcm単位で指定された長さがあります。また、フェリーの長さ (L) もわかっています。キューから最大量の車をフェリーに積み込むことができるアルゴリズムを提案する必要があります。各車は、左、中央、または右の 3 つの車線のいずれかを選択できます。車は順番に処理する必要があります - 各車 (先頭から開始) について、どの車線を走行するかを決定する必要があります。キューの前にある車に十分な空きスペースがない場合は、終了します。残りの車両は次のフェリーを待ちます。

貪欲な方法 (first-fit) は、すべての場合で最も効率的というわけではありません (たとえば、L が 5 でキューが 5 2 2 3 3 の場合)。したがって、動的計画法の問題と考える場合、解決策は何かを理解しようとしていました。それでも私は何かを見つけようとしていますが、私が知っているすべての動的アルゴリズム(特にアルゴリズムの紹介から)はその問題に適合していないようです。

ご提案いただきありがとうございます。:)

1 つのアルゴリズムに問題があります。

n 個の箱が与えられ、それぞれの箱の重量と強度は固定されています (どちらも kg で与えられます)。ボックスの強度は、ボックスが耐えられる最大重量を示しています。与えられたボックスの最大の山を形成する必要があります (それぞれのボックスの高さは同じです)。k 個のボックス (k <= n) の最長シーケンスである最適解を常に与えるアルゴリズムを提案する必要があります。

まあ、それは私がすでに考え出した解決策です：

1. まず、すべての箱を重さで分類し (最も重いものを一番下に置きます)、それらの山を形成します。
2. 次に、その山を強さで分類します (最も強いものが一番下になります)。
3. 次に、各ボックスについて、底から始めて、その強度が可能な限り、底まで引き下げようとします。
4. 最終的に、上からいくつの箱を取り除かなければならないかを計算する必要があります。これにより、下にあるいくつかの箱が、本来の重量よりもはるかに重いものを運ぶという状況が発生します。

このアルゴリズムは非常にうまく機能しているように見えますが、常に最適な解が得られるかどうかはわかりません。おそらくそうではないでしょう。ナップザック問題の解法に似た動的解法について疑問に思っていましたが、この方法で解けるかどうか確信が持てません。私の問題に最適な下部構造はないようです。

よろしくお願いします。:)

次のようなファイル名に一致する正規表現があります。

追加データなしで、名前とサブネームを抽出したい。私は問題なくデータを抽出することができます。エラーが発生する問題はそのv4部分です (それは av であり、その後の数字であり、どこにも含まれていないバージョンマーカーです)、除外したいのですが、抽出されますサブネームと一緒に…

私の正規表現は次のようになります。

私はこのようなことを試み?ましたが、「」の末尾にがないと機能(?:v\d+ )?し、バージョンがないとファイル名を一致させることができません:

どうすれば機能しますか？

区切り文字（例<と>）の間でテキストを一致させるという一般的な問題には、2つの一般的なパターンがあります。

• 貪欲*または+数量詞を次の形式START [^END]* ENDで使用する<[^>]*>、または
• 怠惰*?または+?数量詞を次の形式START .*? ENDで使用し<.*?>ます。

どちらか一方を優先する特別な理由はありますか？

次の問題は、アルゴリズムの問​​題（問題653）から抜粋したものです。

数のanx2行列が与えられます。配列のどちらの列にも⌈√n.⌉より長いサブシーケンス（連続する配列要素で構成されていない可能性がある）が含まれないように、配列内の行を並べ替えるO（n log n）アルゴリズムを見つけます。

これを解決する方法がわかりません。ある種の分割統治法の繰り返しを使うかもしれないと思いますが、見つけられないようです。

誰かがこれを解決する方法について何かアイデアがありますか？

Prim のアルゴリズムを変更して、最大スパニング ツリーを見つけられるようにしたい

「貪欲な」アルゴリズムに関するチュートリアルを読んでいますが、実際の「トップコーダー」の問題を解決するのに苦労しています。

与えられた問題が「貪欲な」アルゴリズムで解決できることがわかっている場合、解決策をコーディングするのは非常に簡単です。ただし、この問題が「貪欲」であると言われなければ、それを見つけることはできません。

「貪欲な」アルゴリズムで解決される問題の一般的な特性とパターンは何ですか? それらを既知の「貪欲な」問題 (MST など) の 1 つに減らすことはできますか?

テスト レビューで「貪欲な方法でヒューリスティックに解決されるのは次のうちどれですか?」という質問があります。

A. 重み付けされていないインターバル スケジューリング

B. 0/1 ナップザック

C.フラクショナルナップサック

D. ハフマン符号

0/1 ナップザックが動的プログラミングを使用していることを知っているので、A、C、または D に絞り込むことができました。AとDは貪欲なアルゴリズムを使用して最適に解決できると思うので、私の最善の推測はCでしょう。

これは正しいです？

動的コイン変更問題のコードの最後のセクションを理解するのに苦労しています。以下のコードを含めました。

最後の がわかりませんelse。その時点で貪欲なアルゴリズムを使用する必要がありますか、それともテーブルに既にある値から答えを計算できますか? 私はこの問題を理解しようと懸命に努力してきましたが、かなり近いと思います。この方法では、テーブルを作成し、テーブルに格納された結果を使用して、再帰を使用せずにより大きな問題を解決することにより、一定量の変更を行うために必要な最小量のコインを見つけます。