Variante des Rucksackproblems

Wie würden Sie das Rucksackproblem in einer dynamischen Programmiersituation angehen, wenn Sie jetzt die Anzahl der Elemente im Rucksack durch eine Konstante begrenzen müssten ? Dies ist das gleiche Problem (maximales Gewicht von , jeder Gegenstand hat einen Wert und ein Gewicht ), aber Sie können dem Rucksack nur Gegenstände hinzufügen und müssen natürlich den Wert des Rucksacks optimieren.$p$$W$$v$$w$$p$

Brauchen wir eine 3. Dimension oder könnten wir einen anderen Ansatz ohne sie finden? Ich habe versucht, einfach die Anzahl der Artikel im Rucksack in der Zelle hinzuzufügen und den Maximalwert am Ende mit der Anzahl der Artikel <= aber es ist nicht die BESTE Lösung.$p$

Sehr schöne Frage!

Sie haben zweimal recht:

1. Die Weitergabe der Anzahl der Gegenstände im Rucksack führt nicht zu optimalen Lösungen.
2. Eine Lösung besteht darin, eine dritte Dimension hinzuzufügen. Dies ist ziemlich einfach, aber es ist notwendig, dabei einige Fakten zu berücksichtigen. Beachten Sie jedoch, dass dies nicht die einzige Alternative ist

Im Folgenden gehe ich davon aus, dass Sie mit der auf dynamischer Programmierung basierenden Lösung vertraut sind. Insbesondere werde ich nicht diskutieren, wie die Tabelle rückwärts durchlaufen wird, um die Lösung zu bestimmen .

Konzentrieren wir uns zunächst auf den typischen Fall: Die Anzahl der Elemente ist uneingeschränkt . In diesem Fall erstellen Sie einfach eine Tabelle in der T i , j den optimalen Wert enthält, wenn die Gesamtkapazität des Rucksacks gleich i ist und nur die ersten j Elemente berücksichtigt werden. Von hier:$T$$T_{i,j}$$i$$j$

$T_{i,j} =\max\{T_{i,j-1}, T_{i-w_j,j-1}+v_j\}$

Dabei stehen und für das Gewicht und den Wert des ten Elements. Wennv j j C ist die Gesamtkapazität Ihres Rucksacks und es gibt insgesamt N Gegenstände. Die optimale Lösung ist durch T C , N gegeben . Es ist bekannt, dass dieser Algorithmus in pseudo-polynomieller Zeit ausgeführt wird, und eine seiner Schönheiten besteht darin, dass nur die Kombinationen berücksichtigt werden, die zur maximalen Kapazität passen.$w_j$$v_j$$j$$C$$N$$T_{C, N}$

Dies reicht jedoch nicht aus, wenn Sie Ihre Einschränkung hinzufügen: eine maximale Anzahl von Elementen . Der Grund dafür ist, dass die vorherige Wiederholungsformel unterschiedliche Kombinationen von Elementen nicht berücksichtigt:$p$

1. Erstens, wenn dann ist T i , j = ( T i - w j , j - 1 + v j ), so dass das j- te der Artikel wird trotz der maximalen Anzahl der Elemente in die Tornister hinzugefügt betrachtet, $T_{i,j-1}<(T_{i-w_j,j-1}+v_j)$$T_{i,j}=(T_{i-w_j,j-1}+v_j)$$j$$p$--- damit Sie möglicherweise gegen Ihre Einschränkung verstoßen. Nun, Sie könnten hier versucht sein, die vorhergehende Formel anzuwenden und die Anzahl der bei jedem Schritt eingefügten Elemente zu verfolgen und keine weiteren hinzuzufügen, wenn die Anzahl der Elemente im Rucksack überschreitet, aber,$p$
2. Zweitens, wenn dann ist T i , j = T i , j - 1, so dass dieses Element nicht hinzugefügt wird, aber das könnte ein großer Fehler sein im Falle der optimalen Lösung T i , j - $T_{i,j-1}>(T_{i-w_j,j-1}+v_j)$$T_{i,j}=T_{i,j-1}$$T_{i,j-1}$besteht bereits aus der maximalen Anzahl von Gegenständen, die in den Rucksack gesteckt werden sollen. Der Grund ist, dass wir nicht richtig vergleichen: einerseits, um die optimale Lösung zu erhalten, die aus Elementen besteht, die unter den vorherigen ausgewählt wurden ( j - 1 ) ; Zum anderen, um das j- te Element einzufügen und zusätzlich die beste Teilmenge mit ( p - 1 ) Elementen unter den vorherigen ( j - 1 ) zu betrachten .$p$$(j-1)$$j$$(p-1)$$(j-1)$

Damit besteht eine erste Lösung darin, eine dritte Dimension hinzuzufügen. Für Ihren Fall sei die optimale Lösung, wenn die Kapazität des Rucksacks i beträgt , nur die ersten j Elemente berücksichtigt werden und nicht mehr als k Elemente in den Rucksack gelegt werden dürfen. Jetzt,$T_{i, j, k}$$i$$j$$k$

• Wenn Sie für eine Anzahl von Elementen berechnen , die streng kleiner oder gleich der Anzahl der Elemente sind, die eingefügt werden können ( j ≤ k ), fahren Sie wie gewohnt fort, verwenden Sie jedoch den gleichen Wert von k : T i , j , k = max { T i , j - 1 , k , T i - w j , j - 1 , k + v j$T_{i, j, k}$$j\leq k$$k$$T_{i,j,k} =\max\{T_{i,j-1,k}, T_{i-w_j,j-1,k}+v_j\}$
• Wenn Sie nun für eine Anzahl von Elementen berechnen müssen, die streng größer sind als die Anzahl der Elemente, die eingefügt werden können ( j > k ), dann gilt: T i , j , k = max { T i , j - 1 , k , T i - w j , j - 1 , k - 1 + v j$T_{i, j, k}$$j> k$$T_{i,j,k} =\max\{T_{i,j-1,k}, T_{i-w_j,j-1,k-1}+v_j\}$

Der erste Ausdruck sollte klar sein. Die zweite funktioniert, da die -te Schicht der Tabelle T die beste Kombination von ( k - 1 ) Elementen unter den ersten ( j - 1 ) verfolgt, wie oben erforderlich.$(k-1)$$T$$(k-1)$$(j-1)$

Eine effiziente Implementierung dieses Algorithmus muss für alle k berechnen . Beachten Sie, dass die vorhergehenden Wiederholungsbeziehungen die Schicht k mit ( k - 1 ) in Beziehung setzen und es daher möglich ist, zwischen zwei aufeinanderfolgenden Schichten zu wechseln (z. B. wenn Sie an der optimalen Lösung mit k = 4 interessiert sind, verwenden Sie nur zwei aufeinanderfolgende Schichten: 0 und 1, 1 und 2, 2 und 3, 3 und 4 und du bist fertig). Mit anderen Worten, dieser Algorithmus benötigt doppelt so viel Speicher wie der herkömmliche Ansatz, der auf dynamischer Programmierung basiert, und kann daher immer noch in Pseudo-Polynom-Zeit ausgeführt werden.$T_{i, j, k}$$k$$k$$(k-1)$$k=4$

Beachten Sie jedoch, dass dies nicht die einzige Lösung ist! Und es gibt noch eine andere, die Sie vielleicht eleganter finden. In den vorhergehenden Formeln haben wir die optimale Lösung gefunden, die aus nicht mehr als Elementen unter den ersten ( j - 1 ) als T i , j - 1 , k - 1 bestand . Es sollte jedoch klar sein, dass dies genau gleich max p = 0 , j - 1 { T i , p$(k-1)$$(j-1)$$T_{i, j-1, k-1}$$\max\limits_{p=0,j-1}\{T_{i, p}\}$nur mit der Originaltabelle !! Das heißt, die optimale Lösung mit nicht mehr als Elementen kann auch abgerufen werden, indem die optimalen Lösungen mit 1 Element, 2 Elementen, 3 Elementen, ... ( j - 1 ) Elementen ... berücksichtigt werden, damit diese Formulierung funktioniert Verfolgen Sie auch die Anzahl der Elemente, die in jeder Teillösung berücksichtigt werden, sodass Sie zwei Ganzzahlen pro Zelle benötigen. Diese Speicherbelegung führt zu genau den gleichen Speicheranforderungen des oben gezeigten Algorithmus (unter Verwendung einer dritten Dimension in Form von Schichten k ) .$k$$(j-1)$$k$

Hoffe das hilft,