数は、私の問題は、次のように減少させることができるメートル消費者

Question

によって消費されています。各項目のサイズはs（正の整数）です。

ステップの間、各消費者はアイテムを選択し、そのサイズを1だけ減らすことができます。 2人の消費者が同じ商品を選ぶことはできず、商品を選択しないままにすることができます（消費者から商品への注入機能を想像してください）。

私の質問：

（すべての項目の大きさが0である）全てのアイテムを消費するneccessary最小のステップ数は何ですか？

注：この問題の複雑さについてはわかりませんが、解決策が最適でない場合は最適です。最適に近い状態で問題ありません。

例：

// First example: 
// number of items 
n = 4; 

// size of each item, itemSizes[i] represents the size of item i 
int[] itemSizes = {1, 1, 2, 4}; 

// number of consumers 
m = 3; 

// the result should be 4 
int result = computeMinimumNumberOfSteps(n, m, itemSizes); 


// Second example: 
// number of items 
n = 4; 

// size of each item, itemSizes[i] represents the size of item i 
int[] itemSizes = {4, 9, 5, 5}; 

// number of consumers 
m = 2; 

// the result should be 13 
int result = computeMinimumNumberOfSteps(n, m, itemSizes); 

私のアプローチ：

私は欲張りなアプローチを使用しています。私はすべてのアイテムまで、以下のステップを繰り返すために使用される消費されています

1. はm最大の項目選択（ソートをし、そのsize != 0最初m項目を選ぶ）
2. 1によってそれらのサイズを減らす（消費）
3. 更新番号ステップ（段階++）

のこれは今私が、遅いようだ：

1. m最大の項目選択（ソートをし、そのsize != 0最初m項目を選ぶ）
2. これらm項目のうち、最小限の値minを見つけます。
3. ステップ数（ステップ+ =分）

これはまだあまりにも遅いと思われる更新

（いくつかを組み合わせるステップを消費する）最小値minによってそれらのサイズを減少させます。私のアプローチについてどう思いますか？これをさらにスピードアップする方法はありますか？

また、この問題はかなり一般的なように見えますが、私の問題を軽減できる既知の問題について知っていますか？あなたが並列マシンの数P、あなたの仕事を横取りすることができます（pmtn）を持っている。すなわち、C _最大、あなたは最大メイクスパンのC _{最大を最小限にしたい| pmtn |}

Answer 1

あなたの問題は、スケジューリング問題のPに相当します。

McNaughtonのルールは、この問題に対する最適な解決法を提供しています.Dave Kargerらの論文Scheduling Algorithmsで参照できます。 （第2.3.1章）。基本的には、D = max（sum（itemsizes）/ m、max（itemSizes））に達するまで、コンシューマーに任意のアイテムを割り当て、次のコンシューマーを続行します。したがって、このアルゴリズムの実行時間はDです。