分区问题暴力算法

Question

我试图在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”

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