将一个3 * K数组划分为K个相等的子数组算法

Question

将一个3 * K数组划分为K个相等的子数组算法

3

我需要将N个元素的数组分成K个相等的子数组，每个子数组包含3个元素，以便找到这些三元组中第二个元素排序后的最大值。

6 <= N <= 300 

K = number of triplets

K * 3 = N

一个例子是：

N = 5,8,1,5,1,2,7,2,9

将创建三个已排序的三元组：1,5,7 1,2,5 2,8,9

这样可以得到所有可能的三元组中的最大结果：(5 + 2 + 8) = 15

我知道这可以用DP技术来解决，但我想知道是否还有其他方法来解决（更有效率）？

- Tal Avissar

1

这个例子有缺陷。数组中有两个5和一个8，但排序后的三元组有一个5和两个8。 - user3386109

@user3386109 - 修复了漏洞。顺便说一下，这并不改变谜题/想法。 - Tal Avissar

也许是这样，但正确地给出示例是向他人传达问题的重要部分。此外，通过手动进行示例并正确解决问题，您通常可以获得有价值的见解。现在三元组与数组匹配，但三元组并不是最优的。 - user3386109

@user3386109，这正是问题所在：如何找到最佳设置？ - Tal Avissar

3个回答

2

第一步似乎是对数组进行排序。

最佳选择的最小元素是位置K + 1（索引K）处的元素，因为您将K个最低元素作为每个数组的第一个元素，然后必须将位置K + 1处的元素放置在其中一个数组的第二个位置上。

最高数字是位置N-1（索引N-2）处的元素，如果您将2个最高元素放入一个数组中，则会发生这种情况。这也是最优的，因为如果您将这些高数字分散在多个数组中，您只会失去价值而没有任何收益。

最后对于中间的数字：我们可以再次使用下一个两个未使用的最高元素来获得最佳价值。

因此，解决方案是获取索引[N-2、N-4、N-6，...，K]处的元素

或者在代码中，由于排序的缘故时间复杂度是O（nlogn），尽管如果数字具有上限（即固定位数），则可以通过使用基数排序理论上获得O（n）。

public int bestSum(int[] arr) {
    int sum = 0;
    Arrays.sort(arr);
    for (int i = 1; i <= arr.length / 3; i++)
        sum += arr[arr.length - 2 * i];
    return sum;
}

- maraca

1

你可以将8 + 5 + 2 = 15分成[1,8,9]、[1,5,7]和[2,2,5]三个部分。 - kaya3

@kaya3 不可以。每个数组中都需要放入4个数字。嗯，好的，看起来你是对的，问题已经改变了，我之前理解有误。 - maraca

1

不符合问题要求：“将N个元素的数组分成K个相等的子数组，每个子数组包含3个元素”。提问者的示例中子数组大小为3，而问题标题中说N = 3K。 - kaya3

@kaya3 已经更正了，问题已经改变。 - maraca

0

我们可以使用动态规划的解决方法来解决它。首先，我们将对数组进行排序。然后我们将遍历数组，并每次计算dp [i] [j] [k]的最优解，其中：

(i + j + k) = m
m是当前元素的位置。
i是目前为止第一组中的元素数
j是目前为止第二组中的元素数
k是目前为止第三组中的元素数

算法：

int ar = {.....}//Given array
int dp[n/3][n/3][n/3] //For memoization,n is the number of given element

for(int i = 1;i <= n/3;i++){
   for(int j = 1;j <= n/3;j++){
      for(int k  = 1;k <= n/3;k++){
         dp[i][j][k]= max(dp[i][j][k], dp[i-1][j][k] + (i == 2)?ar[i+j+k]:0);
         dp[i][j][k]= max(dp[i][j][k], dp[i][j-1][k] + (j == 2)?ar[i+j+k]:0);
         dp[i][j][k]= max(dp[i][j][k], dp[i][j][k-1] + (k == 2)?ar[i+j+k]:0);
      }
   }
}

最后，答案将存储在 dp[n/3][n/3][n/3] 中。

- mahbubcseju

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kaya3 · Accepted Answer

贪心算法被证明是最优的。首先对数组进行排序，使其为[1, 1, 2, 2, 5, 5, 7, 8, 9]。然后构建三元组以最大化三元组中间的元素。第三个元素必须大于或等于中间元素，因此我们选择最大的两个值和最小的一个值。 - 最大的两个值是8和9，因此第一个三元组为1、8、9。 - 剩下的两个最大值是5和7，所以下一个三元组是1、5、7。 - 剩下的两个最大值是2和5，所以最后一个三元组是2、2、5。

这总共得到了8+5+2=15的总和。请注意，我们不需要实际产生分区；在对列表进行排序后，K个中间元素是索引为N-2、N-4、...、N-2K的元素，因此我们可以直接找到它们的总和。

[1, 1, 2, 2, 5, 5, 7, 8, 9]
          ↑     ↑     ↑

现在让我们证明你做不得更好。任何分区都以K个箭头指向排序数组中的元素结束。每个箭头必须与一个更大索引的非箭头配对，否则它不是三元组的中间元素，或者其三元组的第三个元素已经在另一个三元组中使用过了。因此，任何后缀数组中箭头的密度都不能超过1/2。反之，任何符合此后缀密度属性的箭头分配都可以作为一个分区实现，通过霍尔婚姻定理。

考虑一种将箭头分配给数组索引的方法。如果出现模式↑ _ _，则将箭头向右移动一个空格：

[..., x, y, z, ...]
 ...  ↑  _  _  SSS

becomes

[..., x, y, z, ...]
 ...  _  ↑  _  SSS

这不会减少箭头的数字总和，因为 x <= y; 它除了以 y 开头的后缀外，使所有后缀的密度保持相同。以 y 开头的后缀有 A+1 个箭头和 U+1 个非箭头，因此它的密度<= 1/2当且仅当 A+1 <= U+1。这是因为 SSS 的密度 <= 1/2， implying A <= U。

由此可见，模式 ↑ _ ↑ _ ↑ _ 无法通过将某些箭头向右移动（因为它会违反密度限制）或将某些箭头向左移动（因为它会创建 ↑ _ _）来改进。