分区问题蛮力算法

我正试图在bruteforce中为下面的分区问题做伪代码。

一组整数X和一个整数k（k> 1）。 找到X的k个子集，使得每个子集中的数量总和相同，并且没有两个子集具有共同的元素，或者得出结论：不存在这样的k个子集。 问题是NP-Complete

例如，对于X = {2,5,4,9,1,7,6,8}和k = 3，可能的解决方案是：{2,5,7}，{4,9,1}， {6,8}，因为他们全部总和为14。

对于详尽的搜索，我知道通常我们必须搜索每个可能的解决方案并查看目标是否相似。 但由于这是分区问题，这可能会很棘手。

算法蛮力：

Subset= X.sum/K //I had a guess this would make the parition
For int i==1; I <subset; i++ // this would change partition if not found in the first one
If (j=0; I<n; i++)
    Sum == s[i]
    If sum == target 
        Display “found”
    Else 
    “not found”

---

下面是JavaScript中的一个例子，它描述了正数组元素。 该算法弹出堆栈，并通过检查已完成部件的计数来输出结果; 否则，它会依次获取每个数组元素，并将另一组参数添加到堆栈中，其中数组元素是第一个添加到空白部分的元素，另一个元素依次添加到每个尚未填充的部分。 （为了方便起见， result以字符串形式出现，其中部分索引在每个数组元素之前。）

var arr = [2,5,4,9,1,7,6,8]
var k = 3;

var n = arr.length;
var target = arr.reduce( (prev, curr) => prev + curr ) / k;
var sums = [];
for (var i=0; i<k; i++){
  sums[i] = 0;
}

var stack = [[0,sums,0,""]];

while (stack[0] !== undefined){
  var params = stack.pop();

  var i = params[0];
  var sums = params[1];
  var done = params[2];
  var result = params[3];

  if (done == k){
    console.log(result);
    continue;
  } else if (i == n){
    continue;
  }

  var was_first_element = false;

  for (var j=0; j<k; j++){
    if (!was_first_element && sums[j] == 0){
      was_first_element = true;
      var _sums = sums.slice();
      _sums[j] += arr[i];
      stack.push([i + 1,_sums,done + (_sums[j] == target ? 1 : 0),result + j + ": " + arr[i] +", "]);
    } else if (sums[j] != 0 && arr[i] + sums[j] < target && i < n - 1){
      var _sums = sums.slice();
      _sums[j] += arr[i];
      stack.push([i + 1,_sums,done,result + j + ": " + arr[i] +", "]);
    } else if (sums[j] != 0 && arr[i] + sums[j] == target){
      var _sums = sums.slice();
      _sums[j] += arr[i];
      stack.push([i + 1,_sums,done + 1,result + j + ": " + arr[i] +", "]);
    }
  }
}

输出：

/*
0: 2, 1: 5, 0: 4, 1: 9, 2: 1, 2: 7, 2: 6, 0: 8
{2,4,8} {5,9} {1,7,6}

0: 2, 1: 5, 0: 4, 1: 9, 0: 1, 0: 7, 2: 6, 2: 8
{2,4,1,7} {5,9} {6,8}

0: 2, 0: 5, 1: 4, 1: 9, 1: 1, 0: 7, 2: 6, 2: 8
{2,5,7} {4,9,1} {6,8}
*/

---

我将从@ m69提供的评论开始。 既然你知道所有元素都必须被使用，那么你就知道你的分区的总数将等于整个集合的总和。 增加知识，每个分区有相同的总和，那么你可以确定的k分区，每个将需要有totalSum / k的总和。 这提供了一种快速检测许多不能分割成k个子集的集合。 这段代码可能看起来像这样：

if (totalSum % k != 0)
{
    /* The set can't be partitioned into k elements */
}

现在是时候开始构建一些分区了。 我建议使用递归解决方案。 所以我们将从一个函数开始，该函数接受一个数组以及该数组的每个分区应该具有的总和。

check_partition(array, partitionSum)
{
    /* code goes here */
}

递归将有两个基本情况。 首先，如果给定的数组的总和等于分区总和，那么我们的分区是成功的。 在这种情况下，我们将返回数组。

arraySum = sum(array);
if (sum(array) == partitionSum)
{
    return array;
}

另一个基本情况是，如果数组的总和小于分区的目标总和，则该尝试失败。 在这种情况下，我们返回null来表明给定的分区不起作用。

if (sum(array) < partitionSum)
{
    return null;
}

现在编写递归步骤。 对于这一步，我们希望从数组中选取一个元素并构建每个包含此数字的目标的分区。 阵列中最大的元素是最好的元素，因为它将具有最少的分区。 然后，对于该集合中的每个分区，我们希望从较大的数组中删除其中的元素，然后使用该较小的数组再次运行该函数。

maxElementPartitions = buildAllMaxElementPartitions(array, partitionSum);
foreach(partition in maxElementPartitions)
{
    arrayWithoutPartition = removePartition(array, partition)
    resultSet = check_partition(arrayWithoutPartition, partitionSum);
    if (resultSet == null)
    {
        /* It failed down the chain of recursion somewhere */
        /* Move to the next iteration of the loop */
    }
    else
    {
        return = resultSet + partition;
    }
}
/* If the loop exits no results were found */
return null;

这个递归函数将返回一个成功的分区，或者如果不存在，它将返回null。

链接地址: http://www.djcxy.com/p/89529.html

上一篇: Partition Problems Brute Force Algorithm

下一篇: How to modify text that matches a particular regular expression in Python?