[PYTHON] Ich denke, die Grenze des Rucksacks ist nicht das Gewicht, sondern das Volumen w_11 / 22update
Guten Abend (* ´ω ｀) Vielen Dank für Ihre Unterstützung m (_ _) m
Ich forderte den berühmten Rucksack heraus. Beim diagonalen Betrachten des Codes eines Experten Ich habe nur darüber nachgedacht, was ich tun wollte.
KnapSack.py
class Item:
def __init__(self,w=0,p=0):
self.weight=w
self.price=p
items = [ Item(300,400), Item(500,250), Item(200,980),
Item(600,340), Item(900,670), Item(1360,780),
Item(800,570), Item(250,800) ]
def knapsack(i, w):
if i==len(items):
return 0
if w - items[i].weight < 0.0:
return knapsack(i+1, w)
Val_sum0 = knapsack(i+1, w)
Val_sum1 = knapsack(i+1, w - items[i].weight) + items[i].price
return max(Val_sum0,Val_sum1)
p = knapsack(0, 1200)
print("MAXIMUM TOTAL PRICE is",p)
Ob Sie Ihr Gepäck unterbringen oder nicht Betrachten Sie die Anzahl der Versuche (Anzahl der Versuche) als i. Glücklicherweise sind die aufgereihten Gegenstände begrenzt, Es ist ein Problem, den Maximalwert innerhalb einer bestimmten Bedingung zu finden.
Lassen Sie den Rucksack 0 zurückgeben, wenn Sie bis zum Ende versuchen. Rekursives Versprechen, definieren Sie dies im Basisfall.
KnapSack.py
def knapsack(i, w):
if i==len(items):
return 0
Dies macht die Geschichte jedoch nicht so Dabei addieren wir den Preis des Artikels.
Natürlich fügt es nicht auf unbestimmte Zeit hinzu. Der Maximalwert muss innerhalb des definierten Gewichts liegen. Subtrahieren Sie daher jedes Mal, wenn Sie einen Artikel hinzufügen, das Gewicht des Artikels vom definierten Maximalgewicht. Wenn w - Elemente [i] .wiegen <0, Ich habe das Hinzufügen von Elementen [i] aufgegeben, weil es die Gewichtsgrenze überschreitet. Erhöhen Sie i, um zu versuchen, das nächste Element hinzuzufügen.
KnapSack.py
if w - items[i].weight < 0.0:
return knapsack(i+1, w)
Herzlichen Glückwunsch, wie oben erwähnt
- Die Anzahl der Versuche i ist kleiner oder gleich der Anzahl der Elemente
- Überschreiten Sie niemals die Gewichtsgrenze Erst nach dem Löschen der Bedingungen entscheiden Sie, ob Sie Elemente hinzufügen möchten oder nicht. Sie können es in Betracht ziehen.
KnapSack.py
Val_sum0 = knapsack(i+1, w)#Nicht hinzufügen
Val_sum1 = knapsack(i+1, w - items[i].weight) + items[i].price #hinzufügen
return max(Val_sum0,Val_sum1)#Welches ist größer?
In der obigen Beschreibung war ich süchtig nach Val_sum1 = Rucksack (i + 1, w - Artikel [i] .gewicht) + Artikel [i] .Preis. Artikel hinzufügen.Preis zum Rucksack? Was? (ﾟ Д ﾟ) war.
Aber wenn Sie darüber nachdenken, ist der Rucksack ein rekursiver Prozess, so dass er schließlich in den Basisfall fällt. Das ist richtig, es wird 0 sein. Daher wird nur das Ergebnis des Stapelns von items.price zurückgegeben.
Dann, da die obige Beschreibung ** vollständige Suche ** ist, Doppelte Berechnungen wurden eingeschlossen. Ich werde es reduzieren.
Es war zwar möglich, aber es kann subtil sein (lacht)
knapsack.py
class Item:
def __init__(self,w=0,p=0):
self.weight=w
self.price=p
items = [ Item(300,400), Item(500,250), Item(200,980),
Item(600,340), Item(900,670), Item(1360,780),
Item(800,570), Item(250,800) ]
def knapsack(i, w):
if memo[i][w]:#Überprüfen Sie, ob sich in der entsprechenden Zelle des Memos etwas befindet.
return memo[i][w]#Rückgabewert bei Eingabe, Berechnungsreduzierung!!
if i==len(items):
return 0
if w - items[i].weight < 0.0:
return knapsack(i+1, w)
Val_sum0 = knapsack(i+1, w)
Val_sum1 = knapsack(i+1, w - items[i].weight) + items[i].price
memo[i][w] = max(Val_sum0,Val_sum1) #Eine Notiz machen!!
return memo[i][w]#Gibt den Wert zurück, den Sie notiert haben
wgoal = 700
memo = [[[]for k in range(wgoal + 1)] for l in range(len(items)+1)] #Machte einen riesigen Notizblock(Lol)
p = knapsack(0,wgoal)
print("MAXIMUM TOTAL PRICE is",p)
Was ich bisher gelernt habe, ist ein Memo vorzubereiten Es ist eine Herausforderung, die Berechnung zu reduzieren, indem aufgerufen wird, was in der Vergangenheit berechnet wurde.
Das Memo, das ich dieses Mal vorbereitet habe, ist jedoch zu umfangreich (lacht). Was ich gerade aufschreibe Notieren Sie sich den Höchstpreis für das Gewicht bei einer bestimmten Anzahl von Versuchen. Wenn es mehrere Hundert wiegt, ist der Umfang des zu erstellenden Memos groß. Fehler beim Einstellen des Problems !! (* noωno)
Übrigens gibt es auch eine Methode, die keine Wiederholung verwendet.
knap_dp.py
N = 8 #number of backs
w =[300, 500, 200, 600, 900, 1360, 800, 250]
v =[400, 250, 980, 340, 670, 780, 570, 800]
wgoal = 700
memo = [[0]*(wgoal+1)for l in range(N+1)]
for i in range(N):
for j in range(wgoal+1):
if j < w[i]:
memo[i+1][j] = memo[i][j]
else:
memo[i+1][j] = max(memo[i][j],memo[i][j-w[i]]+v[i])
print("MAXIMUM TOTAL PRICE is",memo[N][wgoal])
Das Outfit war sehr erfrischend. Ich habe verschiedene Gewichte mit rekursiver Verarbeitung ausprobiert. Wechseln Sie zur for-Anweisung und zum i-ten Versuch Ich schreibe alle Gewichte auf (es scheint DP zu heißen).
Ich kann das Gefühl nicht leugnen, dass ich lese und schreibe und mich irgendwie bewege. Ich werde versuchen, ein Bild mit etwas mehr Lokalität (* ´ 艸 ｀) zu erstellen.
-11/22_update-------------------------------------------------------------
Nachdenken über den Fehler bei der Problemeinstellung neulich, Ich habe es leicht ein wenig geändert (lacht)
knap_dp.py
N = 3 #number of backs
w =[3, 4, 5]
v =[30, 50, 60]
wgoal = 8
memo = [[0]*(wgoal+1)for l in range(N+1)]
for i in range(N):
for j in range(wgoal+1):
if j < w[i]:
memo[i+1][j] = memo[i][j]
else:
memo[i+1][j] = max(memo[i][j],memo[i][j-w[i]]+v[i])
print(f"i={i},j={j}")
for k in memo:
print(k)
print()
print("MAXIMUM TOTAL PRICE is",memo[N][wgoal])
Ich werde es vorerst ausführen.
Ausführungsergebnis.py
i=0,j=0
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=0,j=1
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=0,j=2
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=0,j=3
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=0,j=4
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=0,j=5
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=0,j=6
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=0,j=7
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=0,j=8
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1,j=0
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1,j=1
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1,j=2
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1,j=3
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1,j=4
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1,j=5
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1,j=6
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1,j=7
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1,j=8
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=2,j=0
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=2,j=1
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=2,j=2
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=2,j=3
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 30, 0, 0, 0, 0, 0]
i=2,j=4
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 30, 50, 0, 0, 0, 0]
i=2,j=5
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 30, 50, 60, 0, 0, 0]
i=2,j=6
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 30, 50, 60, 60, 0, 0]
i=2,j=7
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 30, 50, 60, 60, 80, 0]
i=2,j=8
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 30, 50, 60, 60, 80, 90]
MAXIMUM TOTAL PRICE is 90
Eine Person, die so viel gezeigt und verstanden werden kann, ist ein Genie.
Ich bin ein gewöhnlicher Mensch, also organisiere ich es, während ich ein Bild erstelle.
Stellen Sie sich zunächst ein Memo vor, das Sie selbst erstellt haben.
w ist das Gewicht. Es wird allmählich in Richtung Ziel zunehmen.
Folgen wir dem Programm.
Lass uns dong dong gehen.
Nachdem wir wissen, was wir tun möchten, setzen wir den Rest von N = 0 zusammen.
Versuchen wir N = 1 mit der gleichen Idee.
Ich werde auch N = 2 versuchen.
Ich sehe, 90 ist das Maximum.
Ich habe es geschafft, dem Code zu folgen, aber
Machst du so einen Tisch in deinem Kopf? Jeder ist ein Genie (ﾟ Д ﾟ)
Ich übe nach und nach und gehe stetig (..) φ Memo Memo
Recommended Posts