algorithm - 以下を解決するためのアイデア

Question

図書館には、 で与えられる^thN bookのページ数の本があります。これらの本は、生徒に割り当てられた本のページ数の合計の最大値とページ数の最小値の合計との差が小さくなるように、学生に配布されます。任意の学生に割り当てられた本の中で、与えられた入力の最小値です。また、本は特定の順序で配置されており、この順序は決して変更してはなりません。ib_iK

例えば：

各B[]本のページ数が含まれているとします。

のN=6 K=3 B={3,7,8,2,6,4}場合、出力は、0本 1 と 2 を学生 1 に、本 3 と 4 を学生 2 に、残りを学生 3 に与えることができるようになります。差は0です

同様にB={3,6,8,2,6,4}、最小差は 1 になります。

Answer 1

w=B のページの合計であり、w/n を計算して回答の制限を見つける必要があります。w/n が整数の場合、この問題があることを意味します。それらの合計が w/n に等しい x 要素はありますか? NP問題

Answer 2

これは、貪欲なO(nklogk)アルゴリズムがあなたを始めるためのアイデアです。まず、本を大きいものから小さいものへ並べ替えます。次に、割り当てられていない最大の本を取り、総ページ数が最も少ない子供に割り当てます. すべての本が割り当てられるまで、これを続けます。各本の割り当てでは、合計ページ数に基づいて子供を並べ替える必要があります。