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