Clever-Excel-Forum

Hallo Gemeinde,

hier eine Lösungsaufgabe, zu der ich bisher (auch nach langen probieren) keinen Weg gefunden habe.

Aufgabenstellung: 8 Anbieter haben ein Preis abgegeben für insgesamt 8 Pakete. Die Vergabe ist so, dass jeder Anbieter nur ein Paket liefern soll. Es soll nun die günstigste Kombination gefunden werden. (Anhang)

Hört sich eigentlich einfach an.Rein mathematisch gibt es also 8! (8 Fakultät=40320) Kombinationen.

Habt Ihr eine Idee, wie man hier Exceltechnisch für die Summe das Minimum findet?

Bin auf Eure Lösungsansätze gespannt!Schöne Grüße,
Sebastian

Antwort gelöscht

Hallo,

hier mal eine Variante mit Bruteforce. Geht so - wegen des 'Ziffernstrings' - nur bis N = 9.

Reicht Dir das?

cu, Bernd
--

Code:
Option Explicit

Sub BruteForce()

   Dim t As Single

   t = Timer

   Const N As Integer = 8

   Dim arData As Variant

   Dim strSource As String, strPerm As String, strResult As String

   Dim i As Long, j As Integer

   Dim dblSumAct As Double, dblSumMin As Double

   strSource = "12345678"

   arData = Range("C3").Resize(N, N)

   dblSumMin = 1.79E+308

   For i = 0 To Application.Fact(N) - 1

      strPerm = permutation(i, strSource)

      dblSumAct = 0

      For j = 1 To N

         dblSumAct = dblSumAct + arData(j, CInt(Mid(strPerm, j, 1)))

      Next

      If dblSumAct < dblSumMin Then

         dblSumMin = dblSumAct

         strResult = strPerm

      End If

   Next

   t = Timer - t

   Debug.Print "Indizes der minimalen Summe: "; strResult

   Debug.Print "Minimale Summe:"; dblSumMin

   Debug.Print "Benötigte Zeit in Sekunden:"; t

End Sub

' http://en.wikipedia.org/wiki/Permutation

' Unordered generation

Function permutation(ByVal k As Long, ByVal s As String) As String

   Dim j As Long, i As Long, x As String

   For j = 2 To Len(s)

      i = (k Mod j) + 1

      x = Mid(s, j, 1)

      Mid(s, j, 1) = Mid(s, i, 1)

      Mid(s, i, 1) = x

      k = Int(k / j)

   Next

   permutation = s

End Function

Hallo Bernd,

klasse, vielen Dank!!!
Hatte für die Kombination noch ein wenig gebraucht bis ich rausgefunden hatte, welche Zellen addiert werden. Jetzt habs auch ich verstanden.

Also, vielen Dank nocheinmal!

Schöne Grüße,
Sebastian

Henkelzupfer

BoskoBiati

bst

Henkelzupfer