問題タブ [greedy]

Kruskal の最小スパニング ツリーのアルゴリズムの逆は機能しますか? つまり、すべてのステップで最大の重み (エッジ) を選択するということですか?

最大スパニングツリーを見つけるための他のアイデアはありますか?

わかりました、問題があります。私はさまざまなサイズのボトルのセット「A」を持っており、すべて水で満たされています。次に、さまざまなサイズのボトルの別のセット「B」があり、すべて空です。

各セットの合計容量が同じであることを知って、A から B に水を移動したいと考えています。(つまり、セット A にはセット B と同じ量の水が含まれています)。

もちろん、これ自体は些細なことで、最初のボトルを B に取り、最初のボトルを A に注ぎ、いっぱいになるまで注ぎます。次に、B のボトルにまだ水が入っている場合は、A の 2 番目のボトルに進みます。

ただし、注ぐ回数の合計を最小限に抑えたいです (ボトルから別のボトルに注ぐアクション。水の量に関係なく、各アクションは 1 としてカウントされます)。

これを行うための貪欲なアルゴリズムを見つけたいと思います。それが不可能な場合でも、少なくとも効率的なアルゴリズムを見つけてください。ただし、効率はアルゴリズムの正確さに次ぐものです (次善のソリューションは必要ありません)。

もちろん、この問題は、個人の支出を管理するためのコンピューター プログラムにおける実際の問題の比喩にすぎません。

正規表現を持つ〜このように：

URL が見つかったらキャプチャしたいのですが、何かが見つかりましたが、リンクが取得できません (キャプチャは常に空です)。このように最後に疑問符を削除すると

これは、末尾にリンクがあるものにのみ一致します... 午前 2 時 40 分です... アイデアがありません...

- 編集 -

サンプル入力:

blablabla asd 1234t535 <a href="http://google.com" target="_blank">

期待される出力:

match 0:

「http://google.com」または「」が欲しいだけです

HTMLソースからの特定のスパンタグを一致させようとしています。

タグのlang属性と内部HTMLは、新しい文字列を返す関数のパラメーターとして使用されます。

古いタグ、属性、コンテンツを呼び出された関数の結果に置き換えたい。

件名は次のようになります。

lang属性とコンテンツの値を抽出するために、これらの値を次の式でグループ化します。

正規表現は貪欲になる傾向があるため、この式は、1つのスパンタグとそのコンテンツだけでなく、完全な主題に一致します。

1つのスパンタグだけを一致させるにはどうすればよいですか？

"===text=== and ===text===" のような入力文字列があり、wiki 構文を対応する html タグに置き換えたいと考えています。

入力：

望ましい出力:

しかし、次のコードを使用すると、次の出力が得られます。

問題は、正規表現が貪欲に一致することです。しかし、それらを貪欲にしない方法。

ありがとうございます。ダニー

支配集合 (DS) := 無向グラフ G = (V;E) が与えられた場合、頂点の集合 SV は、V のすべての頂点について、v に隣接する頂点が S に存在する場合、支配集合です。頂点集合全体V は、任意のグラフにおける自明な支配集合です。

ツリーの最小サイズ支配セットを見つけます。

私は数字のピラミッドを持っています。各数字は、関連付けられたポイントの数を表します。欲張りアルゴリズムを使用して、ピラミッドの上部から下部に到達するためのコストが最も低いパスを見つける必要があります。情報に基づいていない検索アルゴリズムと情報に基づいた検索アルゴリズムについて読んだことがありますが、それでも何を選択すればよいかわかりません。この種の問題に最も適しているのは何ですか？貪欲な最良優先探索/A*探索またはその他？これは非常に単純な問題ですが、これらすべてのアルゴリズムを使用して、最適なオプションを知ることはできません。そして、私が言ったように、それは欲張りアルゴリズムでなければなりません。

'a' が 0 回から 'm' 回連続して発生するか、'b' が 0 回から 'n' 回連続して発生するかのいずれかの選択肢に貪欲に一致させたいと考えています。私が行った場合

「b」のシーケンスがある場合、「a {、m}」と一致し、代替の「b {、n}」は見られず、貪欲な一致にならないため、機能しません.

次の問題があります: N 個の整数のセットが与えられた場合、それらを 2 つのほぼ等しいパーティションに分割し、より大きなパーティションの合計が最小になるようにします。これは、1 つの例外を除いて、従来のパーティションの問題とほぼ同じように思えます。

例: N = 4 数値: 20 5 3 1

結果: 15

説明: 最初の数値は 2 で除算され、各半分は 2 つのパーティションのいずれかに配置されます => 最初のパーティション = 10、2 番目のパーティション = 10。2 番目の数値は最初のパーティションに追加されます => 最初のパーティション = 15。最後の 2 つの数字が 2 番目のパーティションに追加されます => 2 番目のパーティション = 14

=> より大きいパーティション (パーティション 1) の合計 = 15。

私が持っているアイデアは、奇数を減らして並べ替え、貪欲なアルゴリズムを使用してそれらを追加し始め、常に2つのパーティションの合計の差を可能な限り最適に保つことです。奇数の処理が終わったら、残っているのは偶数を取り、1 つのパーティションにそれらを完全に追加する方が、それらを 2 で割って 2 つのパーティションの 1 つに追加するよりも最適かどうかを確認することです。

また、次のデータセットについても、アルゴリズムは正しい答えを提供します: N = 2 数字: 16 15

=> 15 を取り、それを最初のパーティションに追加し、次に 16 を取り、それを 2 で割るのが最適ではないことを確認します。したがって、2 番目のパーティションに追加します。

=> 答えは 16 になります。

アルゴリズムが最適な答えを提供しない一連のデータを提供していただければ幸いです。また、改善点を提案していただければ幸いです。

ありがとう！:)

私が書いた次の貪欲なアルゴリズムに苦労しています。アルゴリズムが完全ではないことはわかっていますが、それを改善する方法は本当にわかりません.:

これが問題の定式化です。さまざまな製品を販売するには、企業は "n" 個のライセンスを必要とします。特定の法律により、1 か月に複数の許可を取得することはできません。さらに、許可の費用は毎月増加します。実際、各許可証の費用は現在 $100.00 ですが、許可証 j, (1 ≤ j ≤ n) の費用は毎月 rj > 1 ずつ増加します (rj はパラメーターです)。つまり、最初の 4 か月でライセンスを購入すると 100r4 の費用がかかりますが、たとえば、5 か月でライセンスを取得するには 100(r3)^5 の費用がかかります。最後に、i が j と異なる場合、ri は rj とは異なると仮定します。問題は、与えられた rj (1 ≤ j ≤ n) のセットに対して、総所有コストを最小化するために "n" パーミットをどのような順序で購入するかです。1. この問題を解決するために、貪欲なアプローチを使用して多項式アルゴリズムを開発します。最悪の場合のアルゴリズムを分析します。2. アルゴリズムが最適解を適切に返すことを証明します。3. 次の場合のアルゴリズムを説明してください: n = 3、r1 = 3、r2 = 4、r3 = 2.

ありがとう