Need help in finalizing this Best Fit Algorithm

Question

Excuse me, quick question:

I am using the below routine to find all Combinations of integers that their sum is equal or less than some integer K.

Imagine I have a glass with volume K, and some beer bottles. I am trying to know which bottles I can pick, and get as much beer as possible!

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);
}

Input:

K = 4

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

Current Output:

[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]

But I want more beer choices! Some combinations are not included:

Expected Output:

All the above, plus:

[1, 2, 1.5]

[1, 2, 0.75]

[2, 0.5, 0.75]

[2, 2]

[1, 3]

etc ..

Answer 1

My guess is that this is suboptimal, but you could use a recursive algorithm that produces all possible permutations, checks each one to determine if it's a unique combination, and adds unique solutions to a solution list:

  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);

This produces the following 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

Answer 2

I agree. This does sound like the knapsack problem: determine if excluding or including an item in the knapsack results in a higher value that does not exceed the capacity of the container.