0

既知のサイズのオブジェクトのセットを 3 つのグループに割り当てることができる必要があります。たとえば、次のような順序付きリストが与えられた場合、2 つの分割点または分離点を見つけて、合計が類似する 3 つのグループを作成したいと考えています。

75, 67, 54, 40, 51, 48, 49, 47

各グループの合計はほぼ等しくなければならず、グループ 2 と 3 の合計は、定義された量 (たとえば 10) を超えて最初のグループの合計を超えることはできません。理想的には、最初のグループは他のグループよりもわずかに大きくなります。アイテムの順序は変更できません。各グループは、元のリストの連続した要素から形成されます。各要素は 1 つのグループに配置されます。

この場合の予想される解決策は次のとおりです。

Groups: [75, 67], [54, 40, 51], [48, 49, 47]

Sums: 142, 145, 144 

ユースケースは、フロントエンド レイアウトの既知の高さに基づいて、優先順位付けされたストーリーの列への割り当てを (サーバー側で) 事前に計算します。コンテンツに十分近い高さ (比例的に言えば) を提供するコードを既に持っていますが、グループ化を行う効率的な方法に苦労しています。これがフロントエンドで行われていないのには十分な理由がありますが、おそらく一般的な解決策をフロントエンドでも使用できます。

4

1 に答える 1

1

各グループに割り当てたいおおよその量 (合計 / 3) がわかっている場合、合計が (合計 / 3) に達するまで、リストを反復処理してグループ 1 にオブジェクトを割り当ててから、グループ 2 に対して同じことを行います。その後、残りはグループ 3 に移動します。最終結果がパラメータに適合しない場合があります。たとえば、グループ 2 がグループ 1 をイプシロン以上超える場合があります。この場合、必要に応じてグループ 3 の 1 つまたは 2 つの要素をグループ 2 に交換します。グループ 2 からグループ 1 に 1 つまたは 2 つの要素を交換する必要があります。最後に 12 個未満の要素を交換する必要があることを想定して、全体を O(n) で実行する必要があります。

于 2013-05-17T20:22:20.743 に答える