Эффективно находите все комбинации назначения меньших бинов большим бинам

Вот моя громоздкая рекурсивная попытка избежать дубликатов и выйти раньше из слишком больших сумм. Функция предполагает, что повторяющиеся элементы, а также размеры ячеек представлены сгруппированными и подсчитанными во входных данных. Вместо того, чтобы помещать каждый элемент в каждую корзину, каждый элемент помещается только в одну из повторяющихся ячеек; и каждый элемент с дубликатами разделяется отчетливо.

Например, в моих результатах комбинация [[[1,10,20]],[[4,5,10,30]]] появляется один раз; в то время как в примере 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]]]

Эта проблема встречается достаточно часто, поэтому большинство систем логического программирования с ограничениями включают предикат для ее явного моделирования. В OPTMODEL и CLP мы называем это упаковать:

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. Таким образом, он может внезапно переключаться с очень быстрого на очень медленное. Вы также можете решить вариант, в котором не каждый мелкий предмет нужно помещать в большую корзину, создав фиктивную большую корзину с достаточной вместимостью, чтобы вместить всю коллекцию мелких предметов.

Как видно из раздела «Подробности» руководства, алгоритмы, которые быстро решают практические задачи, непросты, и детали их реализации имеют большое значение. Мне неизвестны какие-либо библиотеки CLP, написанные на Javascript. Лучше всего обернуть CLP в веб-службу и вызвать эту службу из кода Javascript.