分区问题蛮力算法

Question

我正在尝试用暴力破解下面的分区问题的伪代码。

a set of integers X and an integer k (k >1). Find k subsets of X such that the numbers in each subset sum to the same amount and no two subsets have an element in common, or conclude that no such k subsets exist. The problem is NP-Complete

For example, with X = {2, 5, 4, 9, 1, 7, 6, 8} and k = 3, a possible solution would be: {2, 5, 7}, {4, 9, 1}, {6, 8} because all of them sum up to 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”

Answer 1

这里是 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}
*/

Answer 2

我将从@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 */
}

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

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

另一种基本情况是，如果数组的总和小于分区的目标总和，则此尝试失败。在这种情况下，我们 return 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;

此递归函数将 return 成功分区，或者如果 none 存在，它将 return 为空。

分区问题蛮力算法

Partition Problems Brute Force Algorithm

theory

algorithm

complexity-theory

computer-science

set