有效地找到将较小的箱子分配给较大的箱子的每个组合

Question

假设我有 7 个小垃圾箱，每个垃圾箱中的弹珠数量如下：

var smallBins = [1, 5, 10, 20, 30, 4, 10];

我将这些小垃圾箱分配给 2 个大垃圾箱，每个大垃圾箱的最大容量如下：

var largeBins = [40, 50];

我想找到小垃圾箱如何在不超过容量的情况下分布到大垃圾箱中的每种组合（例如，将小垃圾箱 #4、#5 放入大垃圾箱 #2，其余放入 #1）。

约束条件：

每个小垃圾桶必须分配给一个大垃圾桶。
一个大垃圾桶可以留空

这个问题很容易在 ~~O(n^m)~~ O(2^n) 时间内解决（见下文）：只需尝试每个组合，如果没有超过容量, 保存解决方案。我想要更快的东西，可以处理可变数量的垃圾箱。我可以使用什么晦涩的图论算法来减少搜索space？

//Brute force
var smallBins = [1, 5, 10, 20, 30, 4, 10];
var largeBins = [40, 50];

function getLegitCombos(smallBins, largeBins) {
  var legitCombos = [];
  var assignmentArr = new Uint32Array(smallBins.length);
  var i = smallBins.length-1;
  while (true) {
    var isValid = validate(assignmentArr, smallBins, largeBins);
    if (isValid) legitCombos.push(new Uint32Array(assignmentArr));
    var allDone = increment(assignmentArr, largeBins.length,i);
    if (allDone === true) break;
  }
  return legitCombos;
}

function increment(assignmentArr, max, i) {
  while (i >= 0) {
    if (++assignmentArr[i] >= max) {
      assignmentArr[i] = 0;
      i--;
    } else {
      return i;
    }
  }
  return true;
}

function validate(assignmentArr, smallBins, largeBins) {
  var totals = new Uint32Array(largeBins.length);
  for (var i = 0; i < smallBins.length; i++) {
    var assignedBin = assignmentArr[i];
    totals[assignedBin] += smallBins[i];
    if (totals[assignedBin] > largeBins[assignedBin]) {
      return false;
    }
  }
  return true;
}
getLegitCombos(smallBins, largeBins);

Answer 1

这个问题经常出现，以至于大多数约束逻辑编程系统都包含一个谓词来对其进行显式建模。在 OPTMODEL 和 CLP 中，我们称之为 pack:

proc optmodel;
    set SMALL init 1 .. 7, LARGE init 1 .. 2;
    num size    {SMALL} init [1 5 10 20 30 4 10];
    num capacity{LARGE} init [40 50];

    var WhichBin {i in SMALL} integer >= 1 <= card(LARGE);
    var SpaceUsed{i in LARGE} integer >= 0 <= capacity[i];

    con pack( WhichBin, size, SpaceUsed );

    solve with clp / findall;

    num soli;
    set IN{li in LARGE} = {si in SMALL: WhichBin[si].sol[soli] = li}; 
    do soli = 1 .. _nsol_;
        put IN[*]=;
    end;
quit;

此代码在我的笔记本电脑上在 0.06 秒内生成所有解决方案：

IN[1]={1,2,3,4,6} IN[2]={5,7}
IN[1]={1,2,3,4} IN[2]={5,6,7}
IN[1]={1,2,3,6,7} IN[2]={4,5}
IN[1]={1,2,5,6} IN[2]={3,4,7}
IN[1]={1,2,5} IN[2]={3,4,6,7}
IN[1]={1,2,4,6,7} IN[2]={3,5}
IN[1]={1,2,4,7} IN[2]={3,5,6}
IN[1]={1,2,4,6} IN[2]={3,5,7}
IN[1]={1,3,4,6} IN[2]={2,5,7}
IN[1]={1,3,4} IN[2]={2,5,6,7}
IN[1]={1,5,6} IN[2]={2,3,4,7}
IN[1]={1,5} IN[2]={2,3,4,6,7}
IN[1]={1,4,6,7} IN[2]={2,3,5}
IN[1]={1,4,7} IN[2]={2,3,5,6}
IN[1]={2,3,4,6} IN[2]={1,5,7}
IN[1]={2,3,4} IN[2]={1,5,6,7}
IN[1]={2,5,6} IN[2]={1,3,4,7}
IN[1]={2,5} IN[2]={1,3,4,6,7}
IN[1]={2,4,6,7} IN[2]={1,3,5}
IN[1]={2,4,7} IN[2]={1,3,5,6}
IN[1]={3,5} IN[2]={1,2,4,6,7}
IN[1]={3,4,7} IN[2]={1,2,5,6}
IN[1]={3,4,6} IN[2]={1,2,5,7}
IN[1]={3,4} IN[2]={1,2,5,6,7}
IN[1]={5,7} IN[2]={1,2,3,4,6}
IN[1]={5,6} IN[2]={1,2,3,4,7}
IN[1]={5} IN[2]={1,2,3,4,6,7}
IN[1]={4,6,7} IN[2]={1,2,3,5}
IN[1]={4,7} IN[2]={1,2,3,5,6}

只需更改前 3 行即可解决其他实例。但是，正如其他人指出的那样，这个问题是 NP-Hard 问题。所以它可以突然从非常快切换到非常慢。您还可以通过创建一个容量足以容纳整个小物品集合的虚拟大垃圾箱来解决并非每个小物品都需要分配给大垃圾箱的版本。

从手册中的"Details"部分可以看出，快速解决实际问题的算法并不简单，其实现细节差异很大。我不知道有任何用 Javascript 编写的 CLP 库。您最好的选择可能是将 CLP 包装在 Web 服务中并从您的 Javascript 代码调用该服务。

Answer 2

这是我为了避免重复并从过大的金额中提前退出而进行的繁琐的递归尝试。该函数假定重复元素以及 bin 大小在输入中分组显示并计数。不是将每个元素放置在每个容器中，而是将每个元素仅放置在重复容器中的一个中；并且每个有重复的元素都被清楚地划分。

例如，在我的结果中，组合 [[[1,10,20]],[[4,5,10,30]]] 出现了一次；而在 Leo 的回答中的 SAS 示例中，两次：一次是 IN[1]={1,3,4} IN[2]={2,5,6,7} 一次是 IN[1]={1,4,7} IN[2]={2,3,5,6}.

不能保证效率或平滑度-运行，但是，因为它几乎没有经过测试。也许堆叠调用而不是递归可以减轻浏览器的负担。

JavaScript代码：

function f (as,bs){

  // i is the current element index, c its count; 
  // l is the lower-bound index of partitioned element
  function _f(i,c,l,sums,res){

    for (var j=l; j<sums.length; j++){
      // find next available duplicate bin to place the element in
      var k=0;
      while (sums[j][k] + as[i][0] > bs[j][0]){
        k++;
      }

      // a place for the element was found          
      if (sums[j][k] !== undefined){
        var temp = JSON.stringify(sums),
            _sums = JSON.parse(temp);
        _sums[j][k] += as[i][0];

        temp = JSON.stringify(res);           
        var _res = JSON.parse(temp);

        _res[j][k].push(as[i][0]);

        // all elements were placed
        if (i == as.length - 1 && c == 1){
          result.push(_res);
          return;

        // duplicate elements were partitioned, continue to next element
        } else if (c == 1){
          _f(i + 1,as[i + 1][1],0,_sums,_res);

        // otherwise, continue partitioning the same element with duplicates
        } else {
          _f(i,c - 1,j,_sums,_res);
        }
      }
    }
  }

  // initiate variables for the recursion 
  var sums = [],
      res = []
      result = [];

  for (var i=0; i<bs.length; i++){
    sums[i] = [];
    res[i] = [];
    for (var j=0; j<bs[i][1]; j++){
      sums[i][j] = 0;
      res[i][j] = [];
    }  
  }

  _f(0,as[0][1],0,sums,res);
  return result;
}

输出：

console.log(JSON.stringify(f([[1,1],[4,1],[5,1],[10,2],[20,1],[30,1]], [[40,1],[50,1]])));

/*
[[[[1,4,5,10,10]],[[20,30]]],[[[1,4,5,10,20]],[[10,30]]],[[[1,4,5,20]],[[10,10,30]]]
,[[[1,4,5,30]],[[10,10,20]]],[[[1,4,10,20]],[[5,10,30]]],[[[1,4,30]],[[5,10,10,20]]]
,[[[1,5,10,20]],[[4,10,30]]],[[[1,5,30]],[[4,10,10,20]]],[[[1,10,20]],[[4,5,10,30]]]
,[[[1,30]],[[4,5,10,10,20]]],[[[4,5,10,20]],[[1,10,30]]],[[[4,5,30]],[[1,10,10,20]]]
,[[[4,10,20]],[[1,5,10,30]]],[[[4,30]],[[1,5,10,10,20]]],[[[5,10,20]],[[1,4,10,30]]]
,[[[5,30]],[[1,4,10,10,20]]],[[[10,10,20]],[[1,4,5,30]]],[[[10,20]],[[1,4,5,10,30]]]
,[[[10,30]],[[1,4,5,10,20]]],[[[30]],[[1,4,5,10,10,20]]]]
*/

console.log(JSON.stringify(f([[1,1],[4,1],[5,1],[10,2],[20,1],[30,1]], [[20,2],[50,1]])));

/*
[[[[1,4,5,10],[10]],[[20,30]]],[[[1,4,5,10],[20]],[[10,30]]],[[[1,4,5],[20]],[[10,10,30]]]
,[[[1,4,10],[20]],[[5,10,30]]],[[[1,5,10],[20]],[[4,10,30]]],[[[1,10],[20]],[[4,5,10,30]]]
,[[[4,5,10],[20]],[[1,10,30]]],[[[4,10],[20]],[[1,5,10,30]]],[[[5,10],[20]],[[1,4,10,30]]]
,[[[10,10],[20]],[[1,4,5,30]]],[[[10],[20]],[[1,4,5,10,30]]]]
*/

这是第二个更简单的版本，它仅在无法放置元素时才尝试终止线程：

function f (as,bs){

  var stack = [],
      sums = [],
      res = []
      result = [];

  for (var i=0; i<bs.length; i++){
    res[i] = [];
    sums[i] = 0;
  }

  stack.push([0,sums,res]);

  while (stack[0] !== undefined){
    var params = stack.pop(),
        i = params[0],
        sums = params[1],
        res = params[2];

    for (var j=0; j<sums.length; j++){
      if (sums[j] + as[i] <= bs[j]){
        var _sums = sums.slice();
        _sums[j] += as[i];

        var temp = JSON.stringify(res);
        var _res = JSON.parse(temp);

        _res[j].push(i);

        if (i == as.length - 1){
          result.push(_res);

        } else {
          stack.push([i + 1,_sums,_res]);
        }
      }
    }
  }

  return result;
}

输出：

var r = f([1,5,10,20,30,4,10,3,4,5,1,1,2],[40,50,30]);
console.log(r.length)

console.log(JSON.stringify(f([1,4,5,10,10,20,30], [40,50])));

162137 

[[[30],[1,4,5,10,10,20]],[[10,30],[1,4,5,10,20]],[[10,20],[1,4,5,10,30]]
,[[10,30],[1,4,5,10,20]],[[10,20],[1,4,5,10,30]],[[10,10,20],[1,4,5,30]]
,[[5,30],[1,4,10,10,20]],[[5,10,20],[1,4,10,30]],[[5,10,20],[1,4,10,30]]
,[[4,30],[1,5,10,10,20]],[[4,10,20],[1,5,10,30]],[[4,10,20],[1,5,10,30]]
,[[4,5,30],[1,10,10,20]],[[4,5,10,20],[1,10,30]],[[4,5,10,20],[1,10,30]]
,[[1,30],[4,5,10,10,20]],[[1,10,20],[4,5,10,30]],[[1,10,20],[4,5,10,30]]
,[[1,5,30],[4,10,10,20]],[[1,5,10,20],[4,10,30]],[[1,5,10,20],[4,10,30]]
,[[1,4,30],[5,10,10,20]],[[1,4,10,20],[5,10,30]],[[1,4,10,20],[5,10,30]]
,[[1,4,5,30],[10,10,20]],[[1,4,5,20],[10,10,30]],[[1,4,5,10,20],[10,30]]
,[[1,4,5,10,20],[10,30]],[[1,4,5,10,10],[20,30]]]

有效地找到将较小的箱子分配给较大的箱子的每个组合

Efficiently find every combination of assigning smaller bins to larger bins

javascript

algorithm

math

graph-theory

mathematical-optimization