algorithm - 分区问题蛮力算法

我正在尝试为蛮力下面的分区问题做伪代码。



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

算法蛮力:

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}
*/