ここでは数学的/アルゴリズム的な問題があります。各サブアレイの合計が数値以下であるように配列を分割する方法を見つける
数字の配列が与えられている場合、各サブアレイの合計が所定の数値以下になるように、5つのサブアレイに分ける方法を見つけます。最初の配列からのすべての数値は、サブ配列の1つに移動し、1つの合計の一部でなければなりません。
だからアルゴリズムへの入力は次のようになります D - を表す各サブアレイ和が小さくなければならない数または等しい A - 異なるサブアレイに分離される数字の配列を表す、との一部となります1つの合計
アルゴリズムの複雑さは多項式でなければなりません。 ありがとうございます。問題のアップ
セット： D：サブアレー Aの上限：初期配列
Aがソートされていないと仮定。 （ヒューリスティック） アルゴリズム：Aの最大要素がdよりも大きい場合、標準ソートalgorithm-> O（nlogn）
2.Checkを使用して昇順に
1.Sort A - >（定数） YESの場合、意味S. S/5かどうかを確認> Dない場合は、A内のすべての要素 3.Sumを続ける解 、 - YESの場合> O（N） 、解 がない場合、
を継続していません4.貪欲なアプローチを使用して、新しいサブアレイAsiを作成し、ソートされたAの次の最大要素ajをAsiに追加します。彼はアジの合計がdを超えない。ソートAからAJを取り除く - > O（N）
繰り返しSTEP4の条件のいずれかが満たされるまで：サブアレイのASI作成I.At
が存在するのみ5- i要素が残っています この場合、残りの要素を個々の部分配列に分割します。完了：
II。 i = 5です。5つのサブアレイが作成されています。
上記のアルゴリズムは、多項式時間ではO（nlogn）で囲まれます。
しかし、このヒューリスティックは、ソリューションが存在する場合でもソリューションを見つけることが保証されていません。 –
これはヒューリスティックなのはなぜですか？ –
P = NP（予期しない方法で）をちょうど解いていない限り、あなたの解はヒューリスティックではありません。あなたは、ベストフィットのビンパッキングアルゴリズムに似た何かをしています。その行に沿ったものは必ずしも機能しません。 –
「サブアレイ」によって「連続スライス」ではなく「サブセット」を意味する場合、この問題の多項式時間アルゴリズムを見つけることはできません（P = NP以外の場合）。 Partition Problemは、両方のセットの合計が等しくなるように、数値のリストをセットに分割することです。それはNP完全であることが知られている。パーティションの問題は、次のように問題になる可能性があります。x1, ..., x_nは、合計が等しくなるように2つのセットに分割する正の数であるとします。 dをこの共通の合計（これは、xiを2で割った合計になります）とします。 x_iを、の3つのコピーを加えることにより、サイズn+3の配列Aに拡張する。明らかに、それぞれの合計がd以下であるように、実際にdに等しい場合は、Aを5つのサブアレイに分割する唯一の方法です。これは、サブアレーのうちの3つが長さ1を有することを必要とし、それぞれが数字dからなる。残りの2つのサブアレイは正確に元のn番のパーティションになります。
一方、数値が何であるか、および/またはサブアレーが必要とする追加の制約がある場合、多項式解が存在する可能性があります。しかし、もしそうなら、制約が何であるかを明確に綴るべきです。
この宿題はありますか？何を試しましたか？ – Imran
あなたは負の値を持つことができますか？あなたは入力の順序を変更できますか？ – AlexITC