javascript - 在完成此最佳拟合算法时需要帮助

Question

打扰一下，快速提问:

我正在使用下面的例程来查找整数的所有组合，它们的总和等于或小于某个整数 K。

假设我有一个容量为 K 的玻璃杯和一些啤酒瓶。我想知道我可以挑选哪些瓶子，并尽可能多地喝啤酒!

let K = 4; // my glass
let Input = [1, 2, 0.5, 1.5, 2, 0.75, 3, 4]; // beer bottles
let allCombinations = [];

for(var i = 0; i < Input.length; i++)
{
    let currentCombination = [];

    if(Input[i] <= K)
        currentCombination.push(Input[i]);

    let difference = K - Input[i];

    for(var j = i + 1; j < Input.length; j++)
    {
        if(Input[j] <= difference)
        {
            currentCombination.push(Input[j]);
            difference -= Input[j];
        }
    }
    allCombinations.push(currentCombination);
}

输入:

K = 4

[1, 2, 0.5, 1.5, 2, 0.75, 3, 4]

当前输出:

[1, 2, 0.5]

[2, 0.5, 1.5]

[0.5, 1.5, 2]

[1.5, 2]

[2, 0.75]

[0.75, 3]

[3]

[4]

但我想要更多的啤酒选择!不包括某些组合:

预期输出:

All the above, plus:

[1, 2, 1.5]

[1, 2, 0.75]

[2, 0.5, 0.75]

[2, 2]

[1, 3]

etc ..

Answer 1

我的猜测是这是次优的，但您可以使用递归算法生成所有可能的排列，检查每个排列以确定它是否是唯一组合，并将唯一的解决方案添加到解决方案列表中:

  combinations = [];
  function getCombinationsLessThan(currentCombination, choices, remainingSum) {

    // Check if currentCombination should be added to the solutions list
    if (remainingSum < 0) {
      return      // Sum is too large; terminate recursion
    } else if (currentCombination.length > 0) {

      currentCombination.sort();    // Sort all combinations so comparison can be made sequentially
      var uniquePermutation = true;

      for (var i=0; i<combinations.length; i++) {

        if (currentCombination.length == combinations[i].length) {

          for (var j=0; currentCombination[j]==combinations[i][j] && j<combinations[i].length; j++);  // Pass

          if (j == currentCombination.length) {
            // For loop got all the way through combinations[i], so currentCombination = combinations[i]
            uniquePermutation = false;
            break;
          }

        }
      }

      if (uniquePermutation) {
        combinations.push(currentCombination);
      }

    }

    for (var i=0; i<choices.length; i++) {

      // Copy choices
      var newChoices = choices.slice();           

      // Cut out the i'th element and add to the current combination
      var newCombination = currentCombination.concat(newChoices.splice(i,1));

      var newRemainingSum = remainingSum - choices[i];
      getCombinationsLessThan(newCombination, newChoices, newRemainingSum);
    
    }
  }

  var k = 4;
  var choices = [1, 2, 0.5, 1.5, 2, 0.75, 3, 4];
  getCombinationsLessThan([], choices, k);
  
  var result = '';
  for (var i=0; i<combinations.length; i++) {
    result += combinations[i] + '\n';
  }
  console.log(result);

这会产生以下结果:

1
1,2
0.5,1,2
0.75,1,2
0.5,1
0.5,1,1.5
0.5,0.75,1,1.5
0.5,0.75,1
1,1.5
0.75,1,1.5
0.75,1
1,3
2
0.5,2
0.5,1.5,2
0.5,0.75,2
1.5,2
2,2
0.75,2
0.5
0.5,1.5
0.5,0.75,1.5
0.5,0.75
0.5,3
1.5
0.75,1.5
0.75
0.75,3
3
4