将数组划分为 K 个子数组，差异最小

Question

免责声明：

描述的问题看起来像是竞赛中的任务。我没有参加其中任何一个，我不知道任何正在进行的比赛，这可能涉及这个问题。如果有的话，我会关闭这个问题以保持公平！

我有一个问题：给定一个值数组 A 和整数 K，将 A 拆分为恰好 K 个不重叠的连续子数组，使得具有最小和的子数组与具有最大和的子数组之间的差异最小。允许A向任意方向旋转任意数

考虑一个例子：

Input: A = [5 1 1 1 3 2], K = 3

Output: [5][1 1 1][3 2], maximum sum = 5, minimum sum = 3, result = 2

我有部分工作代码（非常丑陋，我的错，但这并不意味着生产质量）：

#include <climits>
#include <cstdio>
#include <cstring>

const int max_n = 50;
const int max_k = 20;

int deps[max_n];

int max (int x, int y) {
  return x > y ? x : y;
}

int min (int x, int y) {
  return x < y ? x : y;
}

int sum (int a[], int start, int end) {
  int res = 0;
  for (int i = start; i <= end; ++i) res += a[i];

  return res;
}

int k_partitioning(int k, int n, int deps[]) {
  int res = INT_MAX;
  // consider all possible rotations/shifts
  for(int offset = 0; offset < n; ++offset) {
    for(int l_min = 0; l_min < n; ++l_min) {
      for(int r_min = l_min; r_min < n; ++r_min) {
        // check minimal sum subarray
        int min_sum = sum (deps, l_min, r_min);

        int dp[k][n];
        for (int s = 0; s < k; ++s) {
          for (int q = 0; q < n; ++q) {
            dp[s][q] = 0;
          }
        }
        // assuming that current sum is a target sum
        dp[0][r_min-l_min] = min_sum;

        for(int p = 1; p < k; ++p) {
          for(int l_max = 0; l_max < n; ++l_max) {
            for(int r_max = 0; r_max < n; ++r_max) {
              int max_sum = sum(deps, l_max, r_max);

              if (max_sum >= min_sum) dp[p][r_max] = max(dp[p-1][l_max], max_sum);
            } // l_maxs
          } // r_maxs
        } // partitions
        // printing dp

        // skip incorrect partitioning, when not all K partitions were used
        if (dp[k-1][n-1] == 0) continue;

        // update difference
        res = min (res, dp[k-1][n-1] - min_sum);
      } // end min sum seg
    } // start min sum seg
    //break;
  } // cuts
  return res;
}

int main(int argc, char* argv[]) {
  int k = 0;
  scanf("%d", &k);

  int n = 0;
  scanf("%d", &n);

  for (int i = 0; i < n; ++i) {
    scanf("%d", &deps[i]);
  }

  printf ("%d\n", k_partitioning(k, n, deps));

  return 0;
}

思路很简单：假设当前分区的总和最小，枚举所有可能的最大分区，设置动态规划以生成最小值的最大总和，检查差异。总复杂度：O(K*N^4).

我的问题是它没有通过一些测试，我一直在解决它。有人可以帮我吗？

测试失败，例如：

N = 4, K = 2, A = [6 13 10 2]

更新

此版本应修复一些以前的问题。首先，它删除了 "offsets" 上的浪费循环，并在 l_min 循环的末尾添加了一个数组旋转。其次，我注意到 dp 不能用 0 初始化——这是最小化任务，所以它应该用一些大的值初始化（取决于问题的常量，max_value 这里已经超出了值域).最后，间隔不应再重叠 - 每个总和不包括间隔的左端。然而，它仍然没有产生预期的结果。

#include <climits>
#include <cstdio>
#include <cstring>

const int max_value = 200000;
const int max_n = 50;
const int max_k = 20;

int deps[max_n];

int max (int x, int y) {
  return x > y ? x : y;
}

int min (int x, int y) {
  return x < y ? x : y;
}

int sum (int a[], int start, int end) {
  int res = 0;
  for (int i = start; i <= end; ++i) res += a[i];

  return res;
}

int k_partitioning(int k, int n, int deps[]) {
  int res = max_value;

  for(int l_min = 0; l_min < n; ++l_min) {
    for(int r_min = l_min; r_min < n; ++r_min) {
      int min_sum = sum (deps, l_min+1, r_min);

      int dp[k][n];
      for (int s = 0; s < k; ++s) {
        for (int q = 0; q < n; ++q) {
          dp[s][q] = max_value;
        }
      }
      // assuming that current sum is a target sum
      dp[0][r_min-l_min] = min_sum;

      for(int p = 1; p < k; ++p) {
        for(int l_max = 0; l_max < n; ++l_max) {
          for(int r_max = l_max; r_max < n; ++r_max) {
            int max_sum = sum(deps, l_max+1, r_max);

            if (max_sum >= min_sum) dp[p][r_max] = max(dp[p-1][l_max], max_sum);
          } // l_maxs
        } // r_maxs
      } // partitions

      // skip incorrect partitioning, when not all K partitions were used
      if (dp[k-1][n-1] == max_value) continue;

      // update difference
      res = min (res, dp[k-1][n-1] - min_sum);
    } // end min sum seg

    // rotate an array to consider different starting points
    int tmp[n];
    for (int i = 0; i < n; ++i) {
      int new_idx = i + n + 1;

      tmp[new_idx % n] = deps[i];
    }

    for(int i = 0; i < n; ++i) deps[i] = tmp[i];
  } // start min sum seg

  return res;
}

int main(int argc, char* argv[]) {
  int k = 0;
  scanf("%d", &k);

  int n = 0;
  scanf("%d", &n);

  for (int i = 0; i < n; ++i) {
    scanf("%d", &deps[i]);
  }

  printf ("%d\n", k_partitioning(k, n, deps));

  return 0;
}

Answer 1

好的，我想我做到了！

思路如下：我们假设最小和区间总是从0开始。然后我们开始枚举最大和区间，从最小区间的右边界开始。我们为当前最大间隔构建 DP 问题以确定最小最大总和。之后更新结果并将数组旋转一个。

我的代码在计算每次迭代的当前总和方面并不完美。一个人可以 pre-compute 他们每次都索引他们。

此代码可能有一些错误，但它通过了我的所有测试。

#include <climits>
#include <cstdio>
#include <cstring>

const int max_value = 200000;
const int max_n = 50;
const int max_k = 20;

int deps[max_n];

int max (int x, int y) {
  return x > y ? x : y;
}

int min (int x, int y) {
  return x < y ? x : y;
}

int sum (int a[], int start, int end) {
  int res = 0;

  for (int i = start; i <= end; ++i) res += a[i];

  return res;
}

int k_partitioning(int k, int n, int deps[]) {
  int res = max_value;
  for(int offset = 0; offset < n; ++offset) {
    int l_min = 0;
    for(int r_min = l_min; r_min < n; ++r_min) {
      int min_sum = sum (deps, l_min, r_min);

      int dp[k][n];
      for (int s = 0; s < k; ++s) {
        for (int q = 0; q < n; ++q) {
          dp[s][q] = max_value;
        }
      }
      // assuming that current sum is a target sum
      dp[0][r_min-l_min] = min_sum;

      for(int p = 1; p < k; ++p) {
        for(int l_max = r_min; l_max < n; ++l_max) {
          for(int r_max = l_max; r_max < n; ++r_max) {
            int max_sum = sum(deps, l_max+1, r_max);

            if (max_sum >= min_sum) {
              dp[p][r_max] = min(dp[p][r_max], max(dp[p-1][l_max], max_sum));
            }

          } // l_maxs
        } // r_maxs
      } // partitions

      // skip incorrect partitioning, when not all K partitions were used
      if (dp[k-1][n-1] == max_value) continue;

      // update difference
      res = min (res, dp[k-1][n-1] - min_sum);
    } // end min sum seg
    int tmp[n];
    for (int i = 0; i < n; ++i) {
      int new_idx = i + n - 1;

      tmp[new_idx % n] = deps[i];
    }

    for(int i = 0; i < n; ++i) deps[i] = tmp[i];

  } // start min sum seg
  return res;
}

int main(int argc, char* argv[]) {
  int k = 0;
  scanf("%d", &k);

  int n = 0;
  scanf("%d", &n);

  for (int i = 0; i < n; ++i) {
    scanf("%d", &deps[i]);
  }

  printf ("%d\n", k_partitioning(k, n, deps));

  return 0;
}

Answer 2

现在您的代码已经可以运行了，下面是另一种方法:)

考虑到对于每个 k，我们可以将从 A[i] 向左增长的总和 (sum A[i-j..i]) 与为 f(k-1, i-j-1) 记录的所有可用间隔配对并更新它们 - 对于每个间隔，(low, high)，如果总和大于 high，则 new_interval = (low, sum)，如果总和小于 low，则 new_interval = (sum, high)；否则，间隔保持不变。例如，

i:  0 1 2 3 4 5
A: [5 1 1 1 3 2]

k = 3
i = 3, j = 0
The ordered intervals available for f(3-1, 3-0-1) = f(2,2) are:
  (2,5), (1,6) // These were the sums, (A[1..2], A[0]) and (A[2], A[0..1])
Sum = A[3..3-0] = 1
Update intervals: (2,5) -> (1,5)
                  (1,6) -> (1,6) no change

现在，我们可以通过在前 k 轮中识别和修剪间隔，使此迭代 更有效。

观看：

A: [5 1 1 1 3 2]

K = 1:

  N = 0..5; Intervals: (5,5), (6,6), (7,7), (8,8), (11,11), (13,13)

K = 2:

  N = 0: Intervals: N/A

  N = 1: Intervals: (1,5)

  N = 2: (1,6), (2,5)

    Prune: remove (1,6) since any sum <= 1 would be better paired with (2,5)
           and any sum >= 6 would be better paired with (2,5)

  N = 3: (1,7), (2,6), (3,5)

    Prune: remove (2,6) and (1,7)

  N = 4: (3,8), (4,7), (5,6), (5,6)

    Prune: remove (3,8) and (4,7)

  N = 5: (2,11), (5,8), (6,7)

    Prune: remove (2,11) and (5,8)

对于 k = 2，我们现在留下以下修剪后的记录：

{
  k: 2,
  n: {
    1: (1,5),
    2: (2,5),
    3: (3,5),
    4: (5,6),
    5: (6,7)
  }
}

我们已经将 k = 3 的迭代从 n choose 2 个可能的拆分列表中减少到 n 个相关拆分！

应用于k = 3的通用算法：

for k' = 1 to k
  for sum A[i-j..i], for i <- [k'-1..n], j <- [0..i-k'+1]:
    for interval in record[k'-1][i-j-1]: // records are for [k'][n']
      update interval
  prune intervals in k'

k' = 3
  i = 2
    sum = 1, record[2][1] = (1,5) -> no change

  i = 3
    // sums are accumulating right to left starting from A[i]
    sum = 1, record[2][2] = (2,5) -> (1,5)
    sum = 2, record[2][1] = (1,5) -> no change

  i = 4
    sum = 3, record[2][3] = (3,5) -> no change
    sum = 4, record[2][2] = (2,5) -> no change
    sum = 5, record[2][1] = (1,5) -> no change

  i = 5
    sum = 2, record[2][4] = (5,6) -> (2,6)
    sum = 5, record[2][3] = (3,5) -> no change
    sum = 6, record[2][2] = (2,5) -> (2,6)
    sum = 7, record[2][1] = (1,5) -> (1,7)

答案是 5 与 record[2][3] = (3,5) 配对，产生更新间隔 (3,5)。 reader 的修剪逻辑留待解决。如果我们想继续，这里是 k = 3

的修剪列表

{
  k: 3
  n: {
    2: (1,5), 
    3: (1,5),
    4: (3,5),
    5: (3,5)
  }
}

Answer 3

没有旋转的解：

1) 计算最大值 M 和总数 S[=数组的 44=] - O(n)

2) 假设有一个函数 F(P)，如果在仍有 k (>= 0) 个分区的情况下可以得到一个 Sum P 或更少，则该函数 returns 为真。

3) 使用 F 在 range(M, S) 上进行二分搜索。 - O(log(S-M))

4) F背后的逻辑：把桶装满直到不大于S/K。然后移动到下一个桶。如果还有剩余的物品并且没有剩余的桶，那么答案是错误的 - O(n)

时间复杂度 = O(n) + O(n) * (log(S-M)) = O(n*log(S-M))

旋转解：

对于 [0, 1, ... N-1] 中的所有旋转，计算最小总和。

总时间复杂度 = O(n) * O(nlog(S-M)) = O(n^2*log( S-M))

Answer 4

我终于解决了这个问题：将数组拆分为三个子数组，它可能会对你有所帮助。在这里我将一个数组分成三个子数组 java.

    package com.array2;

    public class SplitArray {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        int a[] = { 1, 2, 3, 5, 4, 6, 9, 8, 15, 52, 4, 6, 89 };

        splitArray(a);

    }

    private static void splitArray(int[] a) {
        // TODO Auto-generated method stub

        int a_l = a.length;

        int[] a1 = new int[a.length / 3];
        int[] a2 = new int[a.length / 3];
        int[] a3 = new int[a.length / 3 + a.length % 3];

        for (int i = 0; i < a3.length; i++) {

            if (i < a1.length) {
                a1[i] = a[i];
                a2[i] = a[a1.length + i];
                a3[i] = a[a1.length + a2.length + i];
            } else {
                a3[i] = a[a1.length + a2.length + i];
            }

        }

    }

}

将数组划分为 K 个子数组，差异最小

Partition an array into K subarrays with minimal difference

c

algorithm

mathematical-optimization

dynamic-programming