問題タブ [greedy]

私はこのテキストを持っています

And部分文字列を含む文字列を取得するか、上記の文字列の (左または右から)Orに( )最も近い文字列を取得したいと思います。ここで、 は数値です。W/digitdigit

上記の例では、(test or best) (apple OR 10a) を取得する必要があります。

N 人の従業員が組織に存在する場合、N 範囲の日付オフセットが与えられます。1-4のようなもの
(つまり、従業員は 1 日目、2 日目、3 日目、4 日目に来ます)
2-6
8-9
..
1-14
各従業員がイベントに参加できるように、最小限の日数でイベントを開催する必要があります。これを行うアルゴリズム（おそらく貪欲）を提案してください。
PS: イベントは 1 日イベントです。

私は、法律書の判例集の編集に取り組んでいます。タグを検索および置換操作に使用できるように HTML に変換しました。現在、Kate で作業しています。テキストは事例の名前を参照し、事例の引用は脚注に記載されています。

<i>Smith v Jones</i>127 ......... [other stuff including newline characters].......</br>127 (1937) 173 ER 406;

以下を使用して、Kateで先読みを行うことができました。

<i>.*</i>([0-9]{1,4}) .+<br/>\1 .*<br/>

...しかし、貪欲の問題に遭遇しました。

テキストがごちゃごちゃしているので、バッチ プロセスに頼るのではなく、段階的に一致を見つける必要があります。

先読み演算子と貪欲でない演算子の両方をサポートする Linux (または Windows) テキスト エディターはありますか? それとも、grep または sed を試す必要がありますか?

3x + 2y <= 10 という方程式が与えられた場合、x + y = 最大で 10 - 3x - 2y が最小になるような x と y の値を見つけます。これはどのように行うことができますか？私はそれを動的計画問題と考えています! しかし、私が正しいかどうかはわかりません。

上記では、x = 0 と y = 5 が答えになります。

ありがとう。

昨日、インタビューに出演しました。私は質問の1つで立ち往生していました。ここでも同じことを尋ねています。

x 軸上の点を示す配列が与えられ、N 個の点があります。Mコインもプレゼント。

任意の 2 点間の最小距離を最大化する必要があります。

私はこの質問に完全に行き詰まっているので、私を助けてください。

私の直感と仮定では、貪欲を使用できない場合は常に A* を使用することになりますが、100% 確実ではありません。A* アルゴリズムを認識して特定する方法について、さらにいくつかの例とパターンが必要です。

あなたが最初にそれを見て、これが貪欲ではないこと、またはわざわざ試してみなくてもA *でなければならないことを知っているとき、誰かがいくつかの特別な極端なケースを与えることができますか.

例: 配列: 4,3,0,1,5 {すべての数字が >=0 であると仮定します。また、配列の各要素は数字に対応します。つまり、配列の各要素は 0 から 9 の間です。 }

上記の配列では、最大数は次のとおりです: 5430 {配列の数字 5、4、3、および 0 を使用}

私のアプローチ:

3 で割り切れるには、桁の合計が 3 で割り切れる必要があります。したがって、

1. ステップ-1: 配列からすべてのゼロを削除します。
2. ステップ-2: これらのゼロは最後に来ます。{合計には影響しないため、最大数を見つける必要があります}
3. ステップ-3: 桁数が MAXIMUM で、桁の合計が MAXIMUM で、合計が 3 で割り切れる配列の要素のサブセット (ゼロを除く) を見つけます。
4. STEP-4: 必要な数字は、上記の見つかったセットの数字を降順に並べたものです。

したがって、主なステップはSTEP-3です。つまり、合計がMAXで3で割り切れるMAXIMUM可能な要素数を含むサブセットを見つける方法です。

ステップ 3 は、すべての要素を取り、合計が 3 で割り切れるまでセット内の最小の要素を削除し続けるという GREEDY CHOICE によって実行できるのではないかと考えていました。

しかし、この貪欲な選択が機能するとは確信していません。

私のアプローチが正しいかどうか教えてください。もしそうなら、Step-3のやり方を教えてください。

また、他の可能な/効率的なアルゴリズムを提案してください。

これは一種の出発点ですが、実際にはシナリオをカバーしているとは思いませんが、カバーしている場合は、必要なものに適用する方法に頭を悩ませることができず、混乱しすぎます。.使用するかどうかわから.....ないので、貪欲で不正確な定量化をどのように達成するかがわかりません。

正規表現は私の頭を回転させます...

重複の可能性：
重複する間隔のシーケンスで最大合計を見つけるアルゴリズム

私は次の修正されたアクティビティスケジューリング（欲張りアプローチ）の問題を解決していました：

開始時間Siとfiを含むn個のアクティビティのセットSが与えられた場合、 i番目のアクティビティの終了時間。また、重みwiを考えると、i番目のアクティビティを実行するためにFooが獲得したコスト。

問題は、 fooの収益を最大化するアクティビティを選択することです。fooが獲得できる最大コストを返す必要があります。Fooは一度に1つのアクティビティにしか対応できないと想定します。

ノート：：

これは、従来のアクティビティ選択の問題に似て います。ここでの唯一の違いは、アクティビティごとに、コストwiが与えられることです。そして、ここでの目標はあまりにも異なります-相互に互換性のあるアクティビティの最大サイズのセットを見つける代わりに、この問題では、fooの総収益を最大化するアクティビティのセットを見つける必要があります。

例

この問題を解決するために、古典的な欲張り活動選択アルゴリズムを変更するにはどうすればよいですか。上記の問題を解決するには、どのロジックを使用する必要がありますか？

文字列のリストを受け取り、結果として最初の 2 つの文字列をタプルとして含むリストを返す Haskell 関数を作成しています。したがって、出力例は次のようになります。

私が次のようにアプローチすることを考えていた方法：

基本的に、リストの最初と2番目のインデックスの要素を選択するだけでよいと考えましたが、エラーが発生しています。ここで何か助けはありますか？