5

私は 2 セットの数字を取得しましたが、SET2には通常より多くのアイテムが含まれています。SET2のカウントがSET1のカウント 以上であることが保証されています。実際には、順序が重要であるため、入力はセットではなくリストです。

私の目標は、 SET2の数字を結合 (合計) / 並べ替えて、SET1とできるだけ同じにすることです。類似度は、すべての位置での偏差の合計として定義します。類似度の計算方法については、この投稿を参照してください。合計が小さいほど良い。

私の最初のアプローチは、すべての組み合わせを試して、最適なものを選ぶことでした. これは非常に小さなセット (特に 2 番目のセット) でのみ機能します。この投稿と Rawling からの回答を参照してください。良い組み合わせを得るためのよりスマートな方法はありますか？私は間違いなく最高のものを必要としません。結果として、良いものは問題ありません。空のサブセットを持つセットは明らかにナンセンスです。極端にバランスの取れていないセットは、私にはあまり有望ではないようです。SET1 は約 8 個のエントリを持つ傾向がありますが、最大 18 個のエントリを持つことができます。SET2 のカウントは、多くの場合、10 を超えます (最大 35)。2 つのセットの数値の合計は等しくなります (丸め誤差を除く)。

良い結果と悪い結果の例を次に示します (すべての可能性があるわけではありません)。

SET1 = { 272370, 194560, 233430 }; SET2 = { 53407.13, 100000, 365634.03, 181319.07 }

      272370            |      194560          |        233430 
---------------------------------------------------------------------
     365634.03         |  100000 + 53407.13   |      181319.07       (best match)
     365634.03         |     181319.07        |  100000 + 53407.13   (good)
     365634.03         |      100000          |181319.07 + 53407.13  (ok)
      53407.13          |365634.03 + 100000    |      181319.07       (bad)
      53407.13          |365634.03 + 181319.07 |        100000        (bad)
.                 |365634.03 + 181319.07 | 53407.13 + 100000    (invalid)
53407.13 + 100000 |365634.03 + 181319.07 |                      (invalid)

前提を説明するのを忘れた場合、または説明が不明確または不完全な場合はお知らせください。また、別の例を提供できることを嬉しく思います。

前もって感謝します！

4

1 に答える 1

1

非常にうまく機能するはずのヒューリスティック：

1. list<int> set1, set2;
2. sort(set2) // decreasing, set2[0] would be the greatest value in set2
3. struct set1item = {set1index, value, list<int> chosen}
4. prepare list<set1item> set1items from set1 //(index = index in set1 list, value = set1[index] and chosen = null)
5. put set1items to some priorityqueue pq // ordered by value
6. for each set2item in set2{
7.     item = pq.first()
8.     item.chosen.add(set2item);
9.     item.value -= set2item;
10.    pq.updateFirst(item)
11.}

次のように動作します: set2 を最高から最低まで反復し、set1 から実際の最高の要素を取得し、set2 から取得した要素でそれを減らし、set2 のこの要素を set1 の結果の要素に追加します。

set1 のすべての要素に空の結果がないかどうかを確認することを忘れないでください。

例 1: Set1 = {20, 9, 7, 3}, Set2 = {7, 6, 6, 4, 2, 2, 2, 2, 2, 2, 2, 2}.

iter1: fromSet2 = 7, Set1 = {20:{}, 9:{}, 7:{}, 3:{}}, fromSet1=20. 20 を 7 減らし、その結果に 7 を足します。更新: Set1 = {13:{7}, 9:{}, 7:{}, 3:{}}.

iter2: fromSet2 = 6, Set1 = {13:{7}, 9:{}, 7:{}, 3:{}}, fromSet1=13. 13 を 6 減らし、その結果に 6 を足します。更新: Set1 = {7:{7, 6}, 9:{}, 7:{}, 3:{}}。

iter3: fromSet2 = 6, Set1 = {7:{7, 6}, 9:{}, 7:{}, 3:{}}, fromSet1=9. 9 を 6 減らし、その結果に 6 を足します。更新: Set1 = {7:{7, 6}, 3:{6}, 7:{}, 3:{}}.

iter4: fromSet2 = 4, Set1 = {7:{7, 6}, 3:{6}, 7:{}, 3:{}}, fromSet1=7. 7 を 4 減らし、その結果に 4 を足します。更新: Set1 = {3:{7, 6, 4}, 3:{6}, 7:{}, 3:{}}.

iter5: fromSet2 = 2, Set1 = {3:{7, 6, 4}, 3:{6}, 7:{}, 3:{}}, fromSet1=7. 7 を 2 減らし、その結果に 2 を足します。更新: Set1 = {3:{7, 6, 4}, 3:{6}, 5:{2}, 3:{}}.

...

于 2013-01-24T14:04:40.433 に答える