algorithm - 配列内の最大要素の最小化

Question

nほとんどの場合、次の操作を実行できる正の整数のサイズの配列がありますN。

• サブ配列を選択し、その要素の値をk(kサブ配列の最小値より小さくなければなりません) だけ減らします。
• このような操作では、サブ配列のサイズに を掛けたコストがかかりますk。
• これらの操作の総コストは を超えてはなりませんM。
• NM は非常に大きくなる可能性があります。

この配列の最大要素を最小化するための効率的なアルゴリズムを教えてください。

Answer 1

与えられた最大値を達成できるかどうかを確認できる関数を作成できれば、最大値で二分探索を使用して解を見つけることができます。(最大値が達成可能になるたびに減少し、達成可能でない場合は増加します)。

チェック関数は次のようになります。

def check(array, M, i, j, max)

これは、i と j の間のすべてを M コストで最大値未満に削減できる場合に true を返します。から始めますi=0, j=len(array), max=max_guess

チェック内で何をするかについて多くのオプションがあります。あなたが試すかもしれません：

possible = check(M/2, i..i+j/2, ..) and check(M/2, i..i+j/2,..)
return possible

ただし、M を両方の半分に分割するのは良い考えではありません。おそらく、二分探索を使用して、M を半分に分割する方法を判断できます。ただし、一部のサブセクションが両方の半分にまたがる可能性があるため、配列を半分に分割することさえできない可能性があるため、おそらくどこで分割する必要がありますか? または、分割のために i,j のすべての組み合わせを試す必要があるかもしれません。

幸運を。

Answer 2

正直なところ、この問題の最適な解決策を見つけることはNP困難であると私はかなり疑っています。これは特に役に立たないことは認めますが、これが含まれているより大きな問題にどのように取り組むかについて、別の見方をするかもしれません。

Answer 3

削減された配列の最大数として x を選択したと仮定すると、配列を取り、そのすべての大きな要素を x に減らし、これらの操作のコストとその数を計算してから、これらの (コストの) 最も安いサブセットを貪欲に結合してみることができます。操作の数が N よりも小さくなるまで要素を繰り返します。コストが M よりも大きくなると、縮小された配列で最大要素が大きくなる必要があります。x については、簡単に二分探索できます。