-4

不要なデータ リピーターの一部を削除するのに役立つ c# プログラムを作成しており、配列内の重複データの検索 の助けを借りて、削除するリピーターが既に見つかりました。今、私たちは他の期間でいくつかのリピーターをキャンセルできるかどうかを確認します. 質問は：

数値の配列があります

{1, 2, 3, 4, 5, 6, 7, ...}, {4, 5, 10, 100}, {100, 1, 20, 50}

一部の数値は他の配列で繰り返すことができ、一部の数値は一意で特定の配列にのみ属することができます。配列から最大 N 個の数値を失う準備ができたら、いくつかの配列を削除したいと考えています。

説明：

  1. {1、2}

  2. {2, 3, 4, 5}

  3. {2, 7}

これらの配列から最大 3 つの数字を失う準備ができています。これは、配列 1 を削除できることを意味します。これは、一意の数字である「1」のみを失うためです。また、配列 1 と 3 を削除すると、数字 "1"、"7" が失われます。配列 3 を削除すると、数字 "7" のみが失われ、3 つ未満の数字が失われます。

私たちの出力では、N が失う準備ができている項目の数である N よりも少ない損失になるという条件で、削除できる配列の最大量を示したいと考えています。

4

2 に答える 2

1

この問題はセット カバー問題(例: N=0 を取る) と同等であるため、一般的に機能する効率的で正確な解はほとんどありません。ただし、実際には、ヒューリスティックと近似で十分であることがよくあります。問題がセット カバーと類似していることを考えると、貪欲なヒューリスティックは自然な出発点です。すべての要素をカバーしたときに停止するのではなく、N 以外のすべての要素をカバーしたときに停止します。

于 2014-12-18T02:12:07.133 に答える
0

最初に各配列の数値を取得する必要があります。これにより、その特定の配列に固有の数値がいくつあるかがわかります。
これを行う簡単な方法はO(n²)、要素ごとに、それが一意であるかどうかすべての配列をチェックする必要があるためです。
配列を並べ替えたり、最初に並べ替えたり、ヒープのようなデータ構造を使用したりすることで、これをより効率的に行うことができます。

その後、特定の数の配列の合計が になるように合計を見つけるだけで済みますN。これはサブセット和
の問題に似ていますが、すべての数値が であるため、それほど複雑ではありません。 したがって、これらの数値を最小から最大に並べ替え、並べ替えられた配列を反復処理して、合計と同じ長さの数値を取得するだけです。N > 0> 0
< N
最後に、収まる数に対応するすべての配列を削除できますN。

于 2014-12-14T22:07:28.830 に答える