Excel中背包的变化
所以，我需要find10个数据点列表的组合总数，加起来至less为100.所有解决这个问题的例子我都find了等于一个数的组合数。 我怎样才能总计高于100的组合？ Excel中没有VBA，这是可行的吗？
另一个想法是计算组合总数（10！）并减去1000以下的数字。 但是，又如何find一个范围内的组合总数呢？
问题陈述：10个数据点（65,52,48,44,42,41,39,38,30,18）总共可以有多less个组合至less100个？
我试过的来源（我不能发布超过2个链接） http://www.tushar-mehta.com/excel/templates/match_values/index.html
找出在一个集合中的数字的组合加起来给定的总数
- 在A1到J1中input10个项目
- 在K1中input公式
=IF(ROW()<512,"0" & DEC2BIN(ROW(),9),"1" & DEC2BIN(ROW()-512,9)) - 复制第1行到第1023行
- 将列K和PasteSpecialValues复制到列L中
- 使用TextToColumns将列Lparsing成列M到V
- 在W1中input
=SUMPRODUCT((A1:J1)*(M1:V1))并复制下来
W列包含所有可能组合的总和。
最后在另一个单元格中input：
=COUNTIF(W:W,">=" & 100)
编辑＃1：
要生成一个36位二进制模式，我使用：
=DEC2BIN(INT(ROW()/2^27),9)&DEC2BIN(INT(MOD(ROW(),2^27)/2^18),9)&DEC2BIN(INT(MOD(ROW(),2^18)/2^9),9)&DEC2BIN(MOD(ROW(),2^9),9)
所以对于20位，只需使用：
=RIGHT(DEC2BIN(INT(ROW()/2^27),9)&DEC2BIN(INT(MOD(ROW(),2^27)/2^18),9)&DEC2BIN(INT(MOD(ROW(),2^18)/2^9),9)&DEC2BIN(MOD(ROW(),2^9),9),20)
编辑＃2：
要使用VBA执行类似TextToColumns的操作 ，请select单元格并运行此macros：
Sub PseudoTextToColumns() Dim r As Range, L As Long, i As Long, t As String For Each r In Selection t = r.Text L = Len(t) For i = 1 To L r.Offset(0, i).Value = Mid(t, i, 1) Next i Next r End Sub
注意：
这不适用于21个项目。
VBA蛮力解决scheme
我会分享下面的蛮力解决scheme，检查所有可能的组合。 对于最多15个条目的小arrays来说，速度足够快。 它解决了您的问题，您可以将其作为任何暴力计算的模型，也可以作为优化和应用更快algorithm的起点。 它也可以作为testing任何优化后的algorithm的基础。
Option Explicit ' Main function. Computes the all combinations and prints those that exceed the target ' Each combination is specified by a mask of bits that specifies whether to take o to leave the entry Function CombinationsByBruteForce(inputArray() As Double, target As Double) As Long Dim mask As Long, count As Long For mask = 1 To 2 ^ (1 + UBound(inputArray)) - 1 If SumByMask(inputArray, mask) > target Then count = count + 1 PrintByMask inputArray, mask End If Next Debug.Print "Total number of successful combinations: " & count CombinationsByBruteForce = count End Function ' computes the sum for a given combination. The combination is specified by a mask of bits ' that tells which entries belong to the combination (the 1 bits) Function SumByMask(inputArray() As Double, mask As Long) As Double Dim bit As Long For bit = 0 To UBound(inputArray) If (mask And (2 ^ bit)) <> 0 Then SumByMask = SumByMask + inputArray(bit) Next End Function ' Prints out the entries belonging to a combination specified by a mask Sub PrintByMask(inputArray() As Double, mask As Long) Dim bit As Long For bit = 0 To UBound(inputArray) If (mask And (2 ^ bit)) <> 0 Then Debug.Print inputArray(bit), Next Debug.Print End Sub
' For testing. An array of doubles and a target are specified. ' The variant array is copied into a Double array to improve speed Sub testing() Dim target As Double: target = 350 ' target number to exceed Dim test: test = Array(65, 52, 48, 44, 42, 41, 39, 38, 30, 18) 'convert to explicit array of Double ReDim inputArray(UBound(test)) As Double Dim i As Long For i = LBound(test) To UBound(test): inputArray(i) = test(i): Next ' Launsh the brute force computation CombinationsByBruteForce inputArray, target End Sub
上述testing的输出 ：
65 52 48 44 42 41 39 38 65 52 48 44 42 41 39 30 65 52 48 44 42 41 38 30 65 52 48 44 42 39 38 30 65 52 48 44 41 39 38 30 65 52 48 42 41 39 38 30 65 52 44 42 41 39 38 30 65 52 48 44 42 41 39 38 30 65 52 48 44 42 41 39 38 18 65 52 48 44 42 41 39 30 18 65 52 48 44 42 41 38 30 18 65 52 48 44 42 39 38 30 18 65 52 48 44 41 39 38 30 18 65 52 48 42 41 39 38 30 18 65 52 44 42 41 39 38 30 18 65 48 44 42 41 39 38 30 18 52 48 44 42 41 39 38 30 18 65 52 48 44 42 41 39 38 30 18 Total number of successful combinations: 18
作为求解器的入口点，您可以尝试一个BIP模型，其中决策variables是掩码的位。 求解器应该应用一些分支和界限或类似的技术来find一个组合。 但是用解算器打印出所有成功的组合似乎要困难得多，因为这不是一个优化问题。