需要帮助才能获得尽可能多的独特啤酒

Question

假设我有一家酒吧，汽车在前往海滩之前停下来取啤酒。每辆车都有一个后备箱尺寸（remainingSum），每瓶啤酒都有一个尺寸（beer.size）

我想为客户提供他们的汽车后备箱可以容纳的啤酒组合选择（AllCombinations），但独特的组合。

例如，输入：

let Beers = [ 
    {id: 1, size: 4},
    {id: 5, size: 1},
    {id: 10, size: 0.5},
    {id: 11, size: 1},
    {id: 12, size: 2},
    {id: 13, size: 1},
];

let TrunkSize = 2;

预期输出

AllCombinations = [ // no duplicates
    [{id: 5, size: 1}, {id: 10, size: 0.5}],
    [{id: 5, size: 1}, {id: 11, size: 1}],
    [{id: 5, size: 1}, {id: 13, size: 1}],
    [{id: 10, size: 0.5}, {id: 11, size: 1}],
    [{id: 10, size: 0.5}, {id: 13, size: 1}],
    [{id: 11, size: 1}, {id: 13, size: 1}],
    [{id: 5, size: 1}],
    [{id: 11, size: 1}],
    [{id: 12, size: 2}],
    [{id: 13, size: 1}],
    [{id: 10, size: 0.5}],
]

当前输出

AllCombinations = [ 
    [{id: 5, size: 1}, {id: 10, size: 0.5}],  // dup a
    [{id: 5, size: 1}, {id: 11, size: 1}],    // dup c
    [{id: 5, size: 1}, {id: 13, size: 1}],    // dup d
    [{id: 10, size: 0.5}, {id: 5, size: 1}],  // dup a
    [{id: 10, size: 0.5}, {id: 11, size: 1}], // dup b
    [{id: 10, size: 0.5}, {id: 13, size: 1}], // dup e
    [{id: 11, size: 1}, {id: 13, size: 1}],   // dup f
    [{id: 11, size: 1}, {id: 10, size: 0.5}], // dup b
    [{id: 11, size: 1}, {id: 5, size: 1}],    // dup c
    [{id: 13, size: 1}, {id: 5, size: 1}],    // dup d
    [{id: 13, size: 1}, {id: 10, size: 0.5}], // dup e
    [{id: 13, size: 1}, {id: 11, size: 1}],   // dup f
    [{id: 5, size: 1}],
    [{id: 11, size: 1}],
    [{id: 12, size: 2}],
    [{id: 13, size: 1}],
    [{id: 10, size: 0.5}]
]

当前函数：

AllCombinations = [];
GetCombinations(currentCombination, beers, remainingSum) 
{ 

    if (remainingSum < 0) 
        return;// Sum is too large; terminate recursion

    else {
        if (currentCombination.length > 0) 
        {
            currentCombination.sort();  
            var uniquePermutation = true;

            for (var i = 0; i < this.AllCombinations.length; i++) 
            {
                if (currentCombination.length == this.AllCombinations[i].length) 
                {
                    for (var j = 0; currentCombination[j] == this.AllCombinations[i][j] && j < this.AllCombinations[i].length; j++);  // Pass

                    if (j == currentCombination.length) {
                        uniquePermutation = false; 
                        break;
                    }
                }
            }

            if (uniquePermutation)
                this.AllCombinations.push(currentCombination);
        }
    }

    for (var i = 0; i < beers.length; i++) {
        var newChoices = beers.slice();       
        var newCombination = currentCombination.concat(newChoices.splice(i, 1)); 
        var newRemainingSum = remainingSum - beers[i].size;
        this.GetCombinations(newCombination, newChoices, newRemainingSum);
    }
}

Answer 1

这是另一种方法：

let Beers = [ 
            {id: 1, size: 4},
            {id: 5, size: 1},
            {id: 10, size: 0.5},
            {id: 11, size: 1},
            {id: 12, size: 2},
            {id: 13, size: 1},
];

let TrunkSize = 2;

// get all combinations (stolen from  )
function combinations(array) {
    return new Array(1 << array.length).fill().map(
        (e1,i) => array.filter((e2, j) => i & 1 << j));
}

// filter them out if the summed sizes are > trunksize
var valids = combinations(Beers).filter(function(el) {
  return el.reduce(function(a,b){return a+b.size;}, 0) <= TrunkSize;
});

console.log(valids);

Answer 2

要获得所有可能的组合而不重复，您可以用一组 N 位来表示您的组合，其中 N = # of .

所以你应该得到一个看起来像这样的 table:

1 告诉您哪些啤酒属于这种可能的组合。然后你只需将它们的大小相加。如果您得到的总和大于 trunkCapacity，则中止该循环。

循环后，检查该组合的总大小是否在限制范围内，并将其添加到组合列表中。

function getCombination(beers, trunkSize) {
  const beersCount = beers.length;
  const combinationsCount = Math.pow(2, beersCount);
  
  const combinations = [];
  
  let i = 0; // Change this to 1 to remove the empty combination that will always be there.
  
  while(i < combinationsCount) {
    const binary = i.toString(2);
    const bits = Array.prototype.concat.apply(Array(beersCount - binary.length).fill(0), binary.split('').map(parseInt));
    
    const combination = [];
    
    let bit = 0;
    let total = 0;
    
    while(bit < beersCount && total <= trunkSize) {
      if (bits[bit]) {
        const beer = beers[bit];

        total += beer.size;
      
        combination.push(beer);
      }
      
      ++bit;
    }
    
    if (total <= trunkSize) {
      combinations.push(combination)
    }
  
    ++i;
  }
  
  return combinations;
}

const combinations = getCombination([ 
  {id: 1, size: 4},
  {id: 5, size: 1},
  {id: 10, size: 0.5},
  {id: 11, size: 1},
  {id: 12, size: 2},
  {id: 13, size: 1},
], 2);

console.log(JSON.stringify(combinations, null, 2));

Answer 3

我已经编辑了您的代码，修复了排序并使用其他数组和字符串化进行检查：

let Beers = [ 
    {id: 1, size: 4},
    {id: 5, size: 1},
    {id: 10, size: 0.5},
    {id: 11, size: 1},
    {id: 12, size: 2},
    {id: 13, size: 1},
];

let TrunkSize = 2;

AllCombinations = [];
var combStrings = []
function GetCombinations(currentCombination, beers, remainingSum) 
{ 

    if (remainingSum < 0) 
        return;// Sum is too large; terminate recursion

    else {
        if (currentCombination.length > 0) 
        {
            currentCombination.sort((a,b)=>{
              return a.id > b.id
            });  
            //var uniquePermutation = true;

            var tmp = currentCombination.map((cc)=>{
                  return cc.id;
               })

            if (combStrings.indexOf(JSON.stringify(tmp)) == -1) {
                this.AllCombinations.push(currentCombination);
                var tmp = currentCombination.map((cc)=>{
                  return cc.id;
                })
                combStrings.push(JSON.stringify(tmp))
            }
        }
    }

    for (var i = 0; i < beers.length; i++) {
        var newChoices = beers.slice();       
        var newCombination = currentCombination.concat(newChoices.splice(i, 1)); 
        var newRemainingSum = remainingSum - beers[i].size;
        this.GetCombinations(newCombination, newChoices, newRemainingSum);
    }
}
GetCombinations([],Beers,TrunkSize)
console.log(AllCombinations,combStrings)

Answer 4

您可以获得所有组合并决定哪些组合符合条件。

function getCombinations(array, sum, length) {

    function fork(i, t) {
        var s = t.reduce((a, b) => a + b.size, 0);
        if (i === array.length) {
            return s <= sum && t.length <= length && result.push(t);
        }
        fork(i + 1, t.concat([array[i]]));
        fork(i + 1, t);
    }

    var result = [];
    fork(0, []);
    return result;
}

var beers = [{ id: 1, size: 4 }, { id: 5, size: 1 }, { id: 10, size: 0.5 }, { id: 11, size: 1 }, { id: 12, size: 2 }, { id: 13, size: 1 }],
    result = getCombinations(beers, 2, 2);

document.getElementById('out').appendChild(document.createTextNode(JSON.stringify(result, 0, 4)));

<pre id="out"></pre>

需要帮助才能获得尽可能多的独特啤酒

Need help in getting as much unique beer as possible

javascript

language-agnostic

recursion

combinations

permutation