分区问题蛮力算法 [英] Partition Problems Brute Force Algorithm

问题描述

我正在尝试使用蛮力解决以下分区问题的伪代码.

I am trying to do the pseudocode for the partition problem below in bruteforce.

一组整数X和一个整数k(k> 1).查找X的k个子集，例如 每个子集中的数字总和相同，没有两个 子集有一个共同的元素，或得出结论认为没有这k个子集 存在.问题是NP完全

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

例如，如果X = {2，5，4，9，1，7，6，8}并且k = 3，则可能 解决方案是:{2，5，7}，{4，9，1}，{6，8}，因为它们全部 总计14.

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.

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

for exhaustive search I know typically we would have to search every possible solution and see if the target is similar. But as this is partition problem this could be tricky.

算法蛮力:

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作为字符串在部分索引位于每个数组元素之前的位置出现.)

Here is an example in JavaScript that asssumes positive array elements. The algorithm pops the stack and outputs the result if it is valid by checking the count of completed parts; otherwise, it takes each array element in turn and adds another set of parameters to the stack, one where the array element is the first addition to an empty part, and one where it's added in turn to each of the parts yet filled. (For convenience, result accrues as a string where the part index precedes each array element.)

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

这篇关于分区问题蛮力算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！