Variation von Knapsack in Excel

Question

Also, ich muss die Gesamtzahl der Kombinationen für eine Liste von 10 Datenpunkten, die bis zu mindestens 100 summieren. Alle Beispiele zu lösen, die ich gefunden habe, geben nur die Anzahl von Kombinationen, die eine Zahl gleich sind. Wie kann ich die Kombinationen, die höher als 100 sind, zusammenfassen? Ist dies ohne VBA in Excel möglich?

Eine andere Idee war die Berechnung der Gesamtzahl der Kombinationen (10!) Und Subtrahieren dieser unter 1.000, um die Zahl zu finden. Aber wieder, wie findet man die Gesamtzahl der Kombinationen in einem Bereich?

Problemstellung: 10 Datenpunkte (65, 52, 48, 44, 42, 41, 39, 38, 30, 18) Wie viele Kombinationen können insgesamt mindestens 100 ergeben?

Quellen Ich habe versucht (Ich kann nicht mehr als 2 Links posten) http://www.tushar-mehta.com/excel/templates/match_values/index.html

Find out which combinations of numbers in a set add up to a given total

Answer 1

VBA Brute Force Lösung

Ich würde die folgende Brute-Force teilen Lösung, die alle möglichen Kombinationen überprüft. Es ist schnell genug auf kleinen Arrays bis zu 15 Einträge oder so. Es löst Ihr Problem und Sie können es als Modell für jede brachiale Berechnung und auch als Ausgangspunkt für die Optimierung und Anwendung schneller Algorithmen nehmen. Es kann auch eine gute Grundlage sein, um einen optimierten Algorithmus zu testen, den Sie später implementieren könnten.

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 

Ausgang für den obigen Test:

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 

Als Einstiegspunkt für die mit dem Solver zu lösen, können Sie ein BIP Modell versuchen, wo Die Entscheidungsvariablen sind die Bits der Maske. Der Löser sollte dann eine Verzweigung und gebundene oder ähnliche Technik anwenden, um eine Kombination zu finden. Aber alle erfolgreichen Kombinationen mit dem Solver auszudrucken scheint mit dem Löser viel schwieriger zu lösen, weil es kein Optimierungsproblem ist.

Answer 2

1. Geben Sie die 10 Elemente in A1 durch J1
2. In K1 geben Sie die Formel =IF(ROW()<512,"0" & DEC2BIN(ROW(),9),"1" & DEC2BIN(ROW()-512,9))
3. Copy Zeile 1 nach unten durch Zeile 1023
4. Copy Spalte K und PasteSpecialValues ​​in Spalte L
5. Verwenden Sie T extToColumns Spalte L in Spalten M durch V
6. In W1 eingeben =SUMPRODUCT((A1:J1)*(M1:V1)) und abschreiben

Spalte W enthält die Summen aller möglichen Kombinationen zu analysieren.

Schließlich wird in einer anderen Zelle, ein:

=COUNTIF(W:W,">=" & 100) 

EDIT # 1:

ein Bit-Binär-Muster zu erzeugen, verwende ich:

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

Also für Bits, benutzen Sie einfach:

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

EDIT # 2:

Um so etwas wie TextToColumns mit VBA zu tun, Wählen Sie die Zellen a nd führen Sie diesen Makro:

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 

HINWEIS:

Dies wird nicht für 21 Einzelteile arbeiten.