3

给定一个正整数数组A ，在第一个部分的和 >= 比第二个部分的和，第二个部分的和 >= 比第三个部分的和的条件下，找到最大连续部分的数量， 等等。

我知道需要动态编程。我想到了计算所有可能的分区然后将该算法转换为记忆版本的蛮力。

另一个想法是向后遍历数组，从最后一个元素作为一个分区开始，然后将元素相加，直到它们的总和 >= 比下一部分的总和。

任何建议都非常受欢迎。

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]

如果你有 7 个作为一个分区，你最终会得到 2 个分区。但是 16,15,(1+5+7) 是更好的解决方案。

我建议你看看Integer/Discrete Programming via Branch and Bound

您从最后一项开始，您的分支是您选择分区的不同选择（最后一项为 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 回答