4

次の問題が発生しましたが、解決策を見つけることができません。

声明：

N 個のワイングラスがあります。各ワイングラスの容量は無限であると仮定されます。各グラスのワインの量は、0 以外の正の整数で、単位は ml です。タイプ 1 の移動は、ガラス i からガラス j への 1 ml の移動として定義されます。タイプ 2 の移動は、グラス i から 1 ml を捨てることと定義されます。タイプ 1 のすべての Move のコストは 1 です。タイプ 2 のすべての手のコストは k です。各グラスのワインの初期量が与えられた場合、各グラスのワインの量が素数 (またはゼロ) になるように、2 種類の動きをいくつか行う必要があります。このような変換の最小コストを出力します。

この問題にどう取り組むか？可能な解決策のアイデアはありますか?

4

2 に答える 2

1

これが私のアイデアの大まかなスケッチです。

素数はこのx/ln(x)のように分布しています。

また、そのページの境界を使用して、そのグラス内のワインの量に対して最も近い素数を見つけます。

これらの数値を見つけたら、あるガラスから別のガラスに移動するための値を表すコストを持つエッジを持つグラフに問題を減らすことができます (タイプ 1 の移動)。そして、ノードはメガネそのものになります。

ここからグラフの問題が残り、このグラフで最小コストのパスについて考える必要があります。あなたの目標は、すべてのメガネが素数である状態につながる最小コストのパスを見つけることです。

それを妨げるグラスがある場合は、それらを飲みます(タイプ2の動き)。ワインはあなたに良いです:)

更新：

チャットで議論した有効な考えのいくつかをここに書きます。

  • 二部マッチングが言及されており、問題をそれに減らすことができる可能性があります
  • 最初に、各 2 つのグラスの間の主要なパーティション (各 2 つのグラスの合計の主要なパーティション) を取得できます。これらのパーティションは、グラフのエッジです。次に、タイプ 2 の動きのエッジも追加します。何らかの方法でコストを関連付けてから、最小フロー アルゴリズムを実行して問題を解決できます。
  • 問題は、最適なソリューションが各グラスに最適な素数パリトンを取得することを意味しない可能性があるため、上記のすべてのエッジが必要なことである可能性もあります。
于 2013-03-06T13:59:02.453 に答える
1

このタイプの問題は動的計画法で解決でき、 Hirschberg のアルゴリズムを使用して解決できる文字列の最小編集距離を計算することに似ています。

ここには実際には 2 つの段階があります。まず、素数の組み合わせの候補を見つけてから、これらの各候補までの最小編集距離を計算する必要があります。編集距離が最も短いものが答えです。

たとえば、16 14 8 などの合計があるとします。最初のステップは、考えられる素数の組み合わせをそれぞれ列挙する必要があることです: { 37 0 0 } { 31 7 0 } など。次に、Hirschberg のアルゴリズムを使用して最小編集を計算します。これらの各候補への距離。

于 2013-03-06T15:34:53.127 に答える