Best Possible Combination Sum Of Predefined Numbers That Smaller Or Equal Nn

I have a list of lengths for pipes and I need fit these lengths within maximum allowed length for the best yield For example the max allowed length is 90 and the pieces I need to m

Solution 1:

Here is one possible solution. But it is a brute force algorithm so it's not as fast as possible.

functionbestComb(nums, target) {
  var combinations = [];
  var sums = [];
  functionloop(idx, comb, sum) {
    if(idx >= nums.length || sum + nums[idx] > target) {
      combinations.push(comb.slice());
      sums.push(sum);
      return;
    }
    for(var i = idx; i < nums.length; i++) {
      if(sum + nums[i] > target) break;
      if(sum + nums[i] === target) {
        combinations.push(comb.slice());
        combinations[combinations.length - 1].push(nums[i]);
        sums.push(sum + nums[i]);
        break;
      }
      comb.push(nums[i]);
      loop(i + 1, comb, sum + nums[i]);
      comb.pop();
    }
  }

  nums = nums.slice();
  nums.sort(function(a,b) {return a - b});
  loop(0, [], 0);

  if(sums.length === 0) returnnull;
  var maxSum = sums[0],
      maxComb = combinations[0];
  for(var i = 1; i < sums.length; i++) {
    if(sums[i] > maxSum || sums[i] === maxSum && combinations[i].length < maxComb.length) {
      maxSum = sums[i];
      maxComb = combinations[i];
    }
  }

  return maxComb;
}

var nums = [25, 60, 13, 48, 23, 29, 27, 22];

var solution = bestComb(nums, 90);

console.log(solution);

Solution 2:

This is based on John Coleman'sVBA code. It will create a list of all 255 (2 -1) candidates and place them in order of best to worst:

Sub MAIN()
    Dim i As Long, st As String
    Dim a(1To8) AsInteger
    Dim ary

    a(1) =25
    a(2) =60
    a(3) =13
    a(4) =48
    a(5) =23
    a(6) =29
    a(7) =27
    a(8) =22

    st = ListSubsets(a)
    ary = Split(st, vbCrLf)

    For i = LBound(ary) +1To UBound(ary) -1
        Cells(i, 2) = Replace(ary(i +1), " ", "")
    Next i

    Call DistributeData
    Call SortData
End Sub

Function ListSubsets(Items As Variant) As String
    Dim CodeVector() AsInteger
    Dim i AsInteger
    Dim lower AsInteger, upper AsInteger
    Dim SubList As String
    Dim NewSub As String
    Dim done AsBoolean
    Dim OddStep AsBoolean

    OddStep =True
    lower = LBound(Items)
    upper = UBound(Items)

    ReDim CodeVector(lower To upper) 'it starts all 0
    Do Until done
        'Add a newsubset according tocurrent contents
        'of CodeVector

        NewSub = ""
        For i = lower To upper
            If CodeVector(i) = 1 Then
                If NewSub = "" Then
                    NewSub = Items(i)
                Else
                    NewSub = NewSub & ", " & Items(i)
                End If
            End If
        Next i
        If NewSub = "" Then NewSub = "{}" 'emptyset
        SubList = SubList & vbCrLf & NewSub
        'now update code vector
        If OddStep Then
            'just flip first bit
            CodeVector(lower) =1- CodeVector(lower)
        Else'first locate first 1
            i = lower
            Do While CodeVector(i) <> 1
                i = i + 1
            Loop
            'done if i = upper:
            If i = upper Then
                done =TrueElse'if not done then flip the *next* bit:
                i = i + 1
                CodeVector(i) = 1 - CodeVector(i)
            End If
        End If
        OddStep = Not OddStep 'toggles between even and odd steps
    Loop
    ListSubsets = SubList
EndFunction

Sub DistributeData()
    Columns("B:B").Select
    Selection.TextToColumns Destination:=Range("B1"), DataType:=xlDelimited, _
        TextQualifier:=xlDoubleQuote, ConsecutiveDelimiter:=False, Tab:=False, _
        Semicolon:=False, Comma:=True, Space:=False, Other:=False, FieldInfo _
        :=Array(Array(1, 1), Array(2, 1), Array(3, 1)), TrailingMinusNumbers:=TrueRange("A1:A255").Formula = "=if(sum(B1:I1)>=90,9999,90-sum(B1:I1))"
End Sub

Sub SortData()
    Range("A1:I255").Select
    Application.CutCopyMode =False
    ActiveWorkbook.Worksheets("Sheet5").Sort.SortFields.Clear
    ActiveWorkbook.Worksheets("Sheet5").Sort.SortFields.Add Key:=Range("A1:A255") _
        , SortOn:=xlSortOnValues, Order:=xlAscending, DataOption:=xlSortNormal
    With ActiveWorkbook.Worksheets("Sheet5").Sort
        .SetRange Range("A1:I255")
        .Header = xlGuess
        .MatchCase =False
        .Orientation = xlTopToBottom
        .SortMethod = xlPinYin
        .Apply
    EndWithEnd Sub

So the best combos are:

{60,29} and {25,13,29,22}

REFERENCE:

John Coleman's Code