3

正の整数の配列Aが与えられた場合、最初のセクションの合計が2番目のセクションの合計よりも大きく、2番目のセクションの合計が3番目のセクションの合計よりも大きいという条件で、連続するセクションの最大数を見つけます。、 等々。

私は動的計画法が必要であることを知っています。考えられるすべてのパーティションを計算し、このアルゴリズムをメモ化されたバージョンに変換するという力ずくのことを考えました。

もう1つのアイデアは、最後の要素を1つのパーティションとして開始し、要素の合計が次のセクションの合計よりも大きくなるまで要素を合計して、配列を逆方向に移動することです。

どんな提案でも大歓迎です。

4

3 に答える 3

2

これは興味深い問題です。パーティションの合計が単調に増加する順序である必要があることを除いて、元のパーティションの問題に似ています。動的計画法の再帰関係は次のように与えられます。

numP[i] = max {numP[i-j] + 1} for those values of j (1<=j<=i) such that sum(A[i-j,i-j+1,...,i] >= lastSum[i-j])
        = 1 for i = 1

lastSum[i] = the sum of the last partition in numP[i] solution.
           = A[0] for i = 1;

lastI[i] = starting index of the last partition in numP[i] solution; // this is needed to obtain the partitions in the solution

ここでは、配列のnumP[i]最初の要素を使用して取得できるパーティションの最大数を表しますi(配列はゼロ インデックスではありません)。配列の要素を考慮してすべての可能な解を再帰的に見つけようとし、ith得られたパーティションの最大数を出力します。j最後のパーティションが開始するインデックスを表します。lastSum[i]でありlastI[i]、既に上で定義されています。

動的プログラミング ソリューションの Java 実装を次に示します。

void getMaxPartitions (int[] A) {

   int len = A.length;
   int[] numP = new int[len+1];
   int[] lastSum = new int[len+1];
   int[] lastI = new int[len+1];

   numP[1] = 1;
   lastSum[1] = A[0];
   lastI[1] = 0;
   for (int i = 2; i <= len; i++) {
     int maxIndex = 0;
     int maxPs = 0;
     int maxSum = 0;
     for(int j = 1; j <= i; j++) {
       int sum = 0;
       for(int k = i-j; k < i; k++) {
         sum += A[k];
       }
       if(sum >= lastSum[i-j]) {
         if(maxPs < numP[i-j] + 1) {
           maxPs = numP[i-j]+1;
           maxSum = sum;
           maxIndex = i-j;
         }
       }
     }
     numP[i] = maxPs;
     lastSum[i] = maxSum;
     lastI[i] = maxIndex;
   }
   System.out.println("max partitions = " + numP[len]);
   int i = len;
   while (i > 0) {
     System.out.println(lastSum[i]);
     i = lastI[i];
   }
}

プログラムは、次の入力についてテストされ、結果は以下のとおりです。

(1) {3,4,7,1,5,4,11}     max partitions = 5 {3,4,8,9,11}
(2) {1,2,3,4,5,6,7,11}   max partitions = 8 {1,2,3,4,5,6,7,11}
(3) {1,1,1,1,1,1,1,1,1}  max partitions = 9 {1,1,1,1,1,1,1,1,1}
(4) {9,8,7,6,5,4,3,2,1}  max partitions = 3 {9,15,21}
(5) {40,8,7,6,5,4,3,2,1} max partitions = 1 {76}
于 2013-03-07T08:59:49.740 に答える
1

質問で提案されているような欲張りアルゴリズムは機能しません。リストの最後の要素は確かにそれ自体のパーティションである必要があると思うかもしれませんが、ここに反例があります。

[16、15、1、5、7]

1つのパーティションとして7がある場合、2つのパーティションになります。しかし、16,15、（1 + 5 + 7）がより良い解決策です。

分枝限定法による整数/離散プログラミングをご覧になることをお勧めします

最後の項目から開始し、ブランチはパーティションを選択するためのさまざまな選択肢です（最後の項目はn）。> =ルールを考慮して部分解の実現可能性を確認し、目的関数はパーティションの数を最大化することです。優れた境界関数は、残りのすべてのアイテムがサイズ1のパーティションであると想定することです。

私が持っているもう一つの提案は、リストを逆にした後に質問を言い換えることです、それはより直感的でしょう。リストを逆にして、ルールを<=に変更し、最後ではなく最初から開始します。

于 2013-03-06T15:57:47.853 に答える
0

最初は貪欲なアルゴリズムを使用するつもりでしたが、実際にはここで動的アルゴリズムを実装する必要があります。

最後から始める方が直感的に簡単に思えます。主なアイデアは、再帰の特定のステップに対して、確立された一連のパーティション、進行中のパーティション、および残りのシーケンスがあるということです。次に、アルゴリズムは、現在のパーティションに次の (逆方向の場合は前の要素。以下のコードで行っていることです) を追加するか、パーティショニングを完了するか、または現在のパーティションをここで終了し、パーティショニング (該当する場合: 現在のパーティションは、このステップで終了する最小合計に達していない可能性があります)。

p分割、現在の位置i、現在のセクションのこれまでの累積合計s、および以前の合計を追跡する必要がありs'ます。

以下は OCaml で可能な実装です (コードはテストされていません):

let  partition_by_growing_sums a =
    let n = Array.length a in
    let rec pbgs p s s' i =
       if i < 0 then  1 + List.length l, l::p
       else let x = a.(i) in
       if x+s >= s' then
         let n1, l1 = pbgs p (x+s) s' (pred i)
         and n2, l2 = pbgs (i::p) 0 (x+s) (pred i) in
         if n1 > n2 then n1, l1 else n2, l2
       else pbgs p (x+s) s' (pred i)
    in pbgs [] 0 0 (pred n)

メモ化の場合、各位置から前方 (または後方) に実行された最適な分割を追跡する必要がありますが、この分割は、その位置に続く (または前の) 分割によって到達される合計に依存するため、メモ化された計算は次の場合にのみ役立ちます。この位置の同じ状態につながる分割。これが非常に効果的かどうかはわかりません。

于 2013-03-06T05:04:58.030 に答える