Algorithmus, um die beste Kombination zu erhalten

Question

Ich habe Artikel mit ID 1, 3, 4, 5, 6, 7. Jetzt habe ich Daten wie folgt. Für jede Zeile gibt es eine offerId. Array of Ids bestehen aus der Kombination der ID in einem Array. Discount ist der Wert für die offerId

offerId : Array of Ids  : Discount 
o1  : [1]    : 45 
o2  : [1 3 4]   : 100 
o3  : [3 5]   : 55 
o4  : [5]    : 40 
o5  : [6]    : 30 
o6  : [6 7]   : 20 

Jetzt muss ich alle offerIds auszuwählen, die mir geben beste Kombination von Ids das heißt maximale Gesamt Rabatt.

Zum Beispiel in obigem Fall: mögliche Ergebnisse können sein:

[o2, o4, o5] maximaler Rabatt ist 170(100 + 40 + 30).

Hinweis. Das Ergebnis offerId sollte so aussehen, dass IDs nicht wiederholt werden. Beispiel für o2,o4,o6 ids sind [1,3,4], [5], [6] alle sind verschieden.

Andere Kombination können sein: o1, o3, 06 für die IDs sind [1], [3,5], [6,7] Jedoch ist die Gesamt 120 (45 + 55 + 20), die weniger als 170 ist wie in den vorangegangenen Fall.

Ich brauche einen Algorithmus/Code, der mir combination of offerIds zu identifizieren helfen, die maximum discount geben wird, wenn man bedenkt, dass jedes Angebot unterschiedliche Ids enthalten soll.

HINWEIS Ich schreibe meinen Code in go Sprache. Aber Lösungen/Logik in jeder Sprache werden hilfreich sein.

HINWEIS: Ich hoffe, dass ich meine Anforderung richtig erklären kann. Bitte kommentieren Sie, wenn zusätzliche Informationen benötigt werden. Vielen Dank.

Answer 1

Hier ist eine dynamische Programmierlösung, die für jede mögliche Teilmenge von IDs die Kombination von Angeboten findet, für die der Rabatt maximal möglich ist. Dies wird Pseudocode sein.

Lassen Sie unsere Angebote Strukturen mit den Feldern offerNumber, setOfItems und discount sein. Für die Zwecke der Implementierung, zuerst geben wir die möglichen Elemente durch ganze Zahlen von Null bis Anzahl der verschiedenen möglichen Elemente (z. B. k) minus eins. Danach können wir setOfItems durch eine Binärzahl der Länge k darstellen. Zum Beispiel, wenn k = 6 und setOfItems = 101110 , enthält dieses Set die Punkte 5, 3, 2 und 1 und schließt die Punkte 4 und 0 aus, da die Bits 5, 3, 2 und 1 Einsen und die Bits 4 und 0 sind sind Nullen.

Jetzt lassen Sie f[s] der beste Rabatt sein, den wir erhalten können, indem Sie genau s von Einzelteilen setzen. Hier kann s eine beliebige ganze Zahl zwischen 0 und 2 ^k - 1 sein, die eine der möglichen Untergruppen darstellt, die eine der 2 ^k darstellt. Lassen Sie p[s] die Liste der Angebote sein, die zusammen erlauben uns Rabatt f[s] für den Satz von Artikeln s zu erhalten. Der Algorithmus geht wie folgt.

initialize f[0] to zero, p[0] to empty list 
initialize f[>0] to minus infinity 
initialize bestF to 0, bestP to empty list 
for each s from 0 to 2^k - 1: 
    for each o in offers: 
     if s & o.setOfItems == o.setOfItems: // o.setOfItems is a subset of s 
      if f[s] < f[s - o.setOfItems] + o.discount: // minus is set subtraction 
       f[s] = f[s - o.setOfItems] + o.discount 
       p[s] = p[s - o.setOfItems] append o.offerNumber 
       if bestF < f[s]: 
        bestF = f[s] 
        bestP = p[s] 

Danach, bestF ist der beste Rabatt und bestP ist die Liste der Angebote, die uns diesen Rabatt zu erhalten.

Die Komplexität ist O (| Angebote | * 2 ^k) wobei k die Gesamtzahl der Elemente ist.

Hier ist eine andere Implementierung, die asymptotisch gleich ist, aber in der Praxis schneller sein kann, wenn die meisten Teilmengen nicht erreichbar sind. Es ist "vorwärts" statt "rückwärts" dynamische Programmierung.

initialize f[0] to zero, p[0] to empty list 
initialize f[>0] to -1 
initialize bestF to 0, bestP to empty list 
for each s from 0 to 2^k - 1: 
    if f[s] >= 0: // only for reachable s 
     if bestF < f[s]: 
      bestF = f[s] 
      bestP = p[s] 
     for each o in offers: 
      if s & o.setOfItems == 0: // s and o.setOfItems don't intersect 
       if f[s + o.setOfItems] < f[s] + o.discount: // plus is set addition 
        f[s + o.setOfItems] = f[s] + o.discount 
        p[s + o.setOfItems] = p[s] append o.offerNumber