预定义数字的最小可能组合总和，其值小于或等于NN

我有一个长度的pipe道列表，我需要适合这些长度在最大允许的长度内，以获得最佳的产量

例如，允许的最大长度是90，我需要做的是：

25，60，13，48，23，29，27，22

对于90以内的最佳匹配，我会有一组这样的数字：

60，29（共89）

27日，25日，13日，23日（共88）

48，22（共70）

我发现这个答案类似的问题，但我不知道如何将其转换为使用Excel或JavaScript或PHP

任何帮助，将不胜感激。

谢谢。

Answer 1

这是一个可能的解决scheme。 但这是一个蛮力algorithm，所以它不是尽可能快。

function bestComb(nums, target) { var combinations = []; var sums = []; function loop(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) return null; 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); 

Answer 2

这是基于John Coleman的 VBA代码。 它将创build一个所有255（2 ⁸ -1）个候选人的名单，并按照从最好到最差的顺序排列：

 Sub MAIN() Dim i As Long, st As String Dim a(1 To 8) As Integer 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) + 1 To 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() As Integer Dim i As Integer Dim lower As Integer, upper As Integer Dim SubList As String Dim NewSub As String Dim done As Boolean Dim OddStep As Boolean OddStep = True lower = LBound(Items) upper = UBound(Items) ReDim CodeVector(lower To upper) 'it starts all 0 Do Until done 'Add a new subset according to current 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 = "{}" 'empty set 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 = True Else '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 End Function 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:=True Range("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 End With End Sub 

所以最好的组合是：

{60,29}和{25,13,​​29,22}

参考：

约翰·科尔曼的守则