Wechseln Sie zu einem Stil, der durch Bearbeiten für jeden Abschnitt hinzugefügt wird.
# -*- coding: utf-8 -*-
n = int(raw_input())
w = map(int,raw_input().split())
v = map(int,raw_input().split())
W = int(raw_input())
################naive vollständige Suche########################
def val_tot(i, j):
if i == n:
res = 0
elif j < w[i]:
res = val_tot(i+1,j)
else:
res = max(val_tot(i+1,j), val_tot(i+1, j-w[i]) + v[i])
return res
print val_tot(0, W)
################Memo########################
import numpy as np
val_tot_list = -1*np.ones((n+1,W+1))
def val_tot_memo(i, j):
if val_tot_list[i,j] !=-1:
return val_tot_list[i,j]
else:
if i == n:
res = 0
elif j < w[i]:
res = val_tot_memo(i+1,j)
else:
res = max(val_tot_memo(i+1,j), val_tot_memo(i+1, j-w[i]) + v[i])
val_tot_list[i,j] = res
return res
print int(val_tot_memo(0, W))
################Allmähliche Formel(DP) ########################
## dp[i][j] = dp[i+1][j]( w[i] > j)
## = max(dp[i+1][j], dp[i+1][j-w[i]] + v[i])
## val_tot_list[n,W] = 0
# import numpy as np
val_tot_list = -1*np.ones((n+1,W+1))
val_tot_list[n,:] = 0*val_tot_list[n,:]
for i in range(n-1,-1,-1):
for j in range(W+1):
if i ==n:
val_tot_list[n,j] = 0
else:
if w[i] > j:
val_tot_list[i][j] = val_tot_list[i+1][j]
else:
val_tot_list[i][j] = max(val_tot_list[i+1][j], val_tot_list[i+1][j - w[i]] + v[i])
print int(val_tot_list[0][W])
Der Berechnungsbetrag beträgt O (2 ^ n), O (nW) bzw. O (nW). Ich bin es immer noch nicht gewohnt, plötzlich eine schrittweise Formel zu formulieren und in den Code zu bringen (ich mache wahrscheinlich einen Fehler im Index), daher möchte ich lernen, eine naive vollständige Suche zu schreiben und dann ein Memo zu erstellen.
# -*- coding: utf-8 -*-
s = raw_input()
t = raw_input()
#### dp[i][j]:Maximale gemeinsame Teilzeichenfolgenlänge für Zeichenfolgen vor dem i-ten von s und vor dem j-ten von t
########################## naive #########################
def lcs(i,j):
if i == 0 or j == 0:
return 0
else:
if s[i-1] == t[j-1]:
return lcs(i-1,j-1) + 1
else:
return max(lcs(i-1,j-1+1), lcs(i-1+1,j-1))
print lcs(len(s),len(t))
##########################Memo##################################
import numpy as np
lcs_list = -1*np.ones((len(s)+1, len(t)+1),dtype = int)
def lcs_memo(i,j):
if lcs_list[i][j] != -1:
return lcs_list[i][j]
else:
if i == 0 or j == 0:
lcs_list[i][j] = 0
return 0
else:
if s[i-1] == t[j-1]:
lcs_list[i][j] = lcs_memo(i-1,j-1)+1
else:
lcs_list[i][j] = max([lcs_memo(i-1,j-1+1), lcs_memo(i-1+1,j-1)])
return lcs_list[i][j]
print lcs_memo(len(s),len(t))
########################## DP ##################################
import numpy as np
lcs_list = -1*np.ones((len(s)+1, len(t)+1),dtype = int)
lcs_list[0,:] = 0*lcs_list[0,:]
lcs_list[:,0] = 0*lcs_list[:,0] # initialize
for i in range(len(s)):
for j in range(len(t)):
if s[i] == t[j]:
lcs_list[i+1,j+1] = lcs_list[i,j]+1
else:
lcs_list[i+1,j+1] = np.max([lcs_list[i+1,j], lcs_list[i,j+1] ])
print lcs_list[-1,-1]
Er sagte: „Ich möchte eine naive vollständige Suche tragen und sie dann notieren.“ DP war jedoch am einfachsten zu diesem Thema zu schreiben. Im Gegensatz zum Rucksackproblem befand sich die Schleife von i und j in Vorwärtsrichtung, sodass die Initialisierung anscheinend leicht zu verstehen war.
Die anderen beiden waren ein wenig verwirrt über die Assoziation zwischen dem lcs-Argument und der Indizierung des Arrays.
# -*- coding: utf-8 -*-
n = int(raw_input())
w = map(int,raw_input().split())
v = map(int,raw_input().split())
W = int(raw_input())
#### dp[i][j] :Maximaler Wert, wenn das Gewicht in der Kombination von Elementen bis zum i-ten j oder weniger beträgt,Das endgültige Berechnungsergebnis ist d[n][W]
####Anfangswert d[0][:] = 0, dp[:][0] = 0 (w_i >=Weil es 1 ist)
####Die schrittweise Formel lautet dp[i+1][j] = max(dp[i][j-k*w[i]] + k*v[i]| k ...i. Anzahl der Artikel)
##########################Volle Suche############################
def dp(i,j):
if i <= 0 or j <= 0:
return 0
else:
return max([dp(i-1,j-k*w[i-1])+ k*v[i-1] for k in xrange(j//w[i-1] + 1)])
print dp(n, W)
##########################Memo############################
import numpy as np
dplist = -1*np.ones((n+1, W+1),dtype=int)
def dp_memo(i,j):
if dplist[i,j] != -1:
return dplist[i,j]
else:
if i <= 0 or j <= 0:
dplist[i,j] = 0
return 0
else:
dplist[i,j] = max([dp_memo(i-1,j-k*w[i-1])+ k*v[i-1] for k in xrange(j//w[i-1] + 1)])
return dplist[i,j]
print dp_memo(n,W)
############################ DP_1 ##########################
import numpy as np
dplist = -1*np.ones((n+1, W+1),dtype=int)
dplist[0,:] = 0
dplist[:,0] = 0
for i in xrange(n):
for j in xrange(W+1):
dplist[i+1,j] = max([dplist[i,j-k*w[i]]+k*v[i] for k in xrange(j//w[i]+1)])
print dplist[n][W]
############################ DP_2 ##########################
# import numpy as np
dplist = -1*np.ones((n+1, W+1),dtype=int)
dplist[0,:] = 0
dplist[:,0] = 0
for i in xrange(n):
for j in xrange(W+1):
if j < w[i]: #### i+Der erste Artikel passt nicht mehr
dplist[i+1,j] = dplist[i,j]
else:
dplist[i+1,j] = max(dplist[i,j], dplist[i+1,j-w[i]] + v[i]) ####Transformation des allmählichen Ausdrucks(page 59).Schleifen können reduziert werden.
print dplist[n][W]
Wie im Ameisenbuch wird die Schleife verdreifacht, wenn Sie DP so schreiben, wie es aus der allmählichen Gleichung stammt. Eine Doppelschleife kann erstellt werden, indem doppelte Berechnungen durch Transformieren der Graduierungsformel vermieden werden.
Selbst wenn es in ein Memo umgewandelt wird, wird es immer noch geloopt, so dass es anscheinend trotzdem notwendig ist, es zu verarbeiten. Ich habe numpy verwendet, nur weil es einfach ist, mit Arrays umzugehen, aber ich denke, es ist besser, nur mit dem eingebauten Material schreiben zu können.
# -*- coding: utf-8 -*-
n = int(raw_input())
w = map(int,raw_input().split())
v = map(int,raw_input().split())
W = int(raw_input())
#########Wenn das Ziel von DP als Reaktion auf den Fall, in dem die Gewichtsbeschränkung eng ist, von Wert zu Gewicht geändert wird##########
########## dp[i + 1][j]:Mindestgewicht, wenn der Preis j bis zum i-ten Artikel beträgt
###########Die endgültige Ausgabe ist dp[n][j] <=Maximum j, das W erfüllt
###########Die schrittweise Formel lautet dp[i+1][j] = min(dp[i][j], dp[i][j-v[i]]+w[i])
###########Der Anfangswert ist dp[0][0] = 0, dp[0][j] = INF =float("INF")
###################Volle Suche################
def dp(i,j):
if i == 0 and j == 0:
return 0
elif j != 0 and i == 0:
return float("INF")
else:
if j < v[i-1]:
return dp(i-1,j)
else:
return min(dp(i-1,j), dp(i-1,j-v[i-1])+w[i-1])
res = 0
for j_val in xrange(sum(v)):
if dp(n,j_val) <= W:
res = j_val
print res
###################Memo################
import numpy as np
dplist = np.ones((n+1, sum(v)+1)) * (-1)
def dp_memo(i,j):
if i == 0 and j == 0:
dplist[i,j] = 0
return 0
elif j != 0 and i == 0:
return float("INF")
elif dplist[i,j] != -1:
return dplist[i,j]
else:
if j < v[i-1]:
dplist[i,j] = dp_memo(i-1,j)
return dplist[i,j]
else:
dplist[i,j] = min(dp_memo(i-1,j), dp_memo(i-1,j-v[i-1])+w[i-1])
return dplist[i,j]
res = 0
for j_val in xrange(sum(v)):
if dp_memo(n,j_val) <= W:
res = j_val
print res
################### DP ##################
import numpy as np
dplist = np.ones((n+1, sum(v)+1)) * (-1)
dplist[0,:] = float("INF")
dplist[0,0] = 0
for i in xrange(n):
for j in xrange(sum(v) +1):
if j < v[i]:
dplist[i+1,j] =dplist[i,j]
else:
dplist[i+1,j] = min(dplist[i,j], dplist[i,j-v[i]]+w[i])
res = 0
for j_val in xrange(sum(v)):
if dplist[n,j_val] <= W:
res = j_val
print res
Dies ist auch die am einfachsten zu schreibende DP.
Entweder lautet die allmähliche Gleichung dp [i] = hogehoge (dp [i + 1]) oder dp [i + 1] = hogehoge (dp [i]).
Ersteres ist einfacher beim Schreiben mit rekursivem und letzteres beim Schreiben mit DP (weniger Verwechslung mit Array- und Funktionsargumenten). Es scheint besser, die schrittweise Formel zu ändern, die gemäß der von Ihnen geschriebenen Formel eingerichtet wird. Selbst im aktuellen Problem, wenn dp [i, j] "das i-te und nachfolgende Element" ist, Da die allmähliche Gleichung dp [i, j] = min ist (dp [i + 1, j], dp [i + 1, j-v [i]] + w [i]), ist es einfach, rekursiv zu schreiben.
# -*- coding: utf-8 -*-
n = int(raw_input())
a = map(int,raw_input().split())
m = map(int,raw_input().split())
K = int(raw_input())
import numpy as np
################ dp[i+1][j]:Maximale Anzahl von i-ten, wenn j bis i-th gemacht wird
################Die schrittweise Formel lautet dp[i+1][j] = dp[i+1][j-a[i]] -1
################ = -1
################ = m[i] (dp[i][j] >= 0)
################Wenn du es nicht schaffst-Setzen Sie 1
dplist = np.ones((len(a)+1,K+1))*(-1)
dplist[0,0] = 0
for i in range(len(a)):
for j in range(K+1):
if dplist[i,j] >= 0:
dplist[i+1,j] = m[i]
elif dplist[i+1,j-a[i]]<= 0:
dplist[i+1,j] = -1
elif j - a[i] < 0:
dplist[i+1,j] = -1 ####### j - a[i] <Wenn es 0 ist, ändert es nichts, ob j erstellt werden kann, selbst wenn das i-te eingegeben wird.(i-1)Wenn es auf die Sekunde gebracht werden kann, wird es verarbeitet, so dass Sie hier nur darüber nachdenken müssen, wenn Sie es nicht schaffen können.
else:
dplist[i+1][j] = dplist[i+1,j-a[i]] -1
print dplist[n,K] >= 0
DP für Bool scheint verschwenderisch zu sein.
Im Bool-Wert DP auf Seite 62 steht, dass es sich um eine Dreifachschleife handelt, da es eine Schleife gibt, die verarbeitet, wie viele a [i] eingefügt werden (O (K \ sum_i m [i]), aber O (nK). \ sum_i m [i]) scheint richtig zu sein).
Wie beim Rucksackproblem ohne Begrenzung der Stückzahl scheint es besser zu sein, zu denken, dass es Abfall gibt, wenn eine Dreifachschleife auftritt. Überlegen Sie, wie Sie die Schleife um die Zahl a [i] beseitigen können.
Ob im DP von bool, das dp [i + 1] [j] ist, ob j bis zum i-ten aufgefüllt werden kann Der Prozess von "dp [i + 1, j-k * a [i]] == gibt es ein wahres k?" Ist die Ursache der Dreifachschleife. Wenn daher dp [i + 1] [j] unter Verwendung des Ergebnisses von dp [i + 1, j-a [i]] bestimmt werden kann, wird die Dreifachschleife unnötig.
Wenn Sie jedoch nur den Bool-Wert haben, können Sie nicht wissen, ob ein [i] noch vorhanden ist, auch wenn dp [i + 1, ja [i]] = True angegeben ist, also dp [i + 1 , j] kann nicht beurteilt werden und es wird ein Eichhörnchen, um die Schleife zu drehen. Dann besteht die Idee darin, die verbleibende Anzahl von a [i] als Array zu haben.
Wie erwartet gibt es nicht genügend Schulungen, um aus der Problemstellung an diesen Punkt zu gelangen. Ist es eine gute Idee, einfach (dumm) zu schreiben (zu denken) und nach Verbesserungen wie oben zu suchen (vielleicht ist es nur ein Grundproblem, also denken Sie an das Muster).
# -*- coding: utf-8 -*-
import numpy as np
a = map(int,raw_input().split())
#####################page 63#########################
### dp[i]: a[i]Die Länge der längsten Unterreihe am Ende
dp = np.ones(len(a),dtype = int) * (-1)
dp[0] = 0
res = 0
for i in range(len(a)):
dp[i] = 1
for j in range(i):
if a[j] < a[i]:
dp[i] = max(dp[i],dp[j] + 1)
res = max(res,dp[i])
print res
#####################page 64: O(n^2)#########################
### dp[i]:Länge ist i+Minimalwert des letzten Elements der Unterspalte von 1
dp = np.ones(len(a),dtype = int) * float("INF")
n = len(a)
for j in xrange(n):
for i in xrange(n):
if i == 0 or dp[i-1] <a[j]:
dp[i] = min(dp[i],a[j])
print len(dp[dp<float("INF")])
#####################page 65: O(n log n)#########################
import bisect #### C++Senken Sie ein_Um die gleiche Operation wie gebunden zu erreichen.
dp = np.ones(len(a),dtype = int) * float("INF")
n = len(a)
for j in xrange(n):
dp[bisect.bisect_left(dp,a[j])] = a[j]
print len(dp[dp<float("INF")])
Die beiden unteren sind schwierig.
Wenn Sie im Fall der Richtlinie auf Seite 64 die Schleife für j drehen, wird das Array vorerst wie folgt gefüllt.
a = {2,1,3,2}
Überlegen Sie, wie die dp-Tabelle aktualisiert werden soll, wenn Sie am Ende von a einen neuen Wert hinzufügen.
Erstens ist dp [0] ein zunehmender Teilstring der Länge 1, daher müssen wir nur das neue minimale Element von a einbringen.
dp [1] ist das kleinste Element am Ende des zunehmenden Teilstrings der Länge 2. Ob der Wert durch Hinzufügen eines neuen Elements aktualisiert wird oder nicht, kann durch dp [1] in a vor dem Hinzufügen und das kleinere der neuen Elemente entschieden werden. Wenn jedoch dp [0] mit einem neuen Element aktualisiert wurde, kann sich das neue Element nicht am Ende der ansteigenden Unterspalte befinden und wird ausgeschlossen (wenn i == 0 oder dp [i-1] <a [j]). ] Teil).
Angenommen, für dp [2] wird dp [1] mit einem neuen Element aktualisiert. Wenn zu diesem Zeitpunkt auch dp [2] aktualisiert wird, wird am Ende des Teilstrings der Länge 2 ein kleinerer Wert angezeigt, was ein Widerspruch ist. Vergleichen Sie das neue Element also nur dann mit dem ursprünglichen dp [1], wenn dp [1] nicht aktualisiert wurde.
Wenn Sie also ein neues Element zu a hinzufügen, sollte dp [i] im Allgemeinen nur mit min (dp [i], a_new) aktualisiert werden, wenn dp [i-1] nicht mit diesem Wert aktualisiert wurde. Gut.
Wenn Sie den Anfangswert in INF angeben, können Sie das Element von a durchlaufen und vom Anfang von dp wie oben beurteilen. Dies ist die Antwort in O (n ^ 2).
Die Methode unter Verwendung der Dichotomie auf Seite 65 besteht darin, dass der von Anfang an zu beurteilende Teil O (log n) ist. Sie müssen dp [i] nicht kleiner als a [j] betrachten, da der Wert der endgültigen dp-Sequenz monoton ansteigt. Daher können Sie nach i suchen, sodass dp [i]> = a [j] von bisect.bisect_left (lower_bound in STL). Aus der Suchmethode wird automatisch dp [i-1] <a [j], dp [i] = min (dp [i], a [j]) = a [j] erfüllt, sodass die Bedingung beurteilt wird. Es kann mit dp [i] = a [j] aktualisiert werden, ohne etwas zu tun.
# -*- coding: utf-8 -*-
import numpy as np
n = int(raw_input())
m = int(raw_input())
M = int(raw_input())
####### dp[i][j]Sei die Anzahl der Methoden, wenn i in j geteilt wird.
#######Die schrittweise Formel lautet dp[i][j] = dp[i-j][j] + dp[i][j-1]
dp = np.zeros((n+1,m+1),dtype = int)
dp[:,1] = 1
for i in xrange(n+1):
for j in xrange(2,m+1):
if i-j >=0:
dp[i][j] = dp[i][j-1] + dp[i-j][j]
else:
dp[i][j] = dp[i][j-1]
print dp[-1][-1]
Zuerst dachte ich über die schrittweise Formel nach, die so aussah, als würde ich an den Rest der Boxen mit der größten Anzahl von Boxen denken, aber sie funktionierte wegen Doppelarbeit nicht. Ich hätte die Duplizierung vielleicht beseitigen können, wenn ich es gut gemacht hätte, aber es ist nicht gut, weil es sowieso O (mn ^ 2) war. (Unzureichende mathematische Fähigkeiten vor dem Programmieren)
Ich bin es gewohnt, von allmählichen Ausdrücken in Code zu fallen.
# -*- coding: utf-8 -*-
import numpy as np
n = int(raw_input())
m = int(raw_input())
a = map(int,raw_input().split())
M = int(raw_input())
dp = np.zeros((n+1,m+1),dtype = int)
dp[0,:a[0]] = 1
dp[:,0] = 1
for i in xrange(n):
for j in xrange(1,m+1):
if j -1 - a[i] >=0:
dp[i+1][j] = dp[i+1][j-1] + dp[i][j] -dp[i][j-1-a[i]]
else:
dp[i+1][j] = dp[i+1][j-1] + dp[i][j]
print dp[-1][-1]
Die schrittweise Formel ist einfach, aber wie reduzieren Sie den Rechenaufwand daraus? Um die Dreifachschleife zu löschen, muss die Summe mit dem bereits berechneten Betrag umgeschrieben werden.
Der Teil des Schreibens von Code mit DP ist durch die Implementierungsleistung oder den allmählichen Ausdruck reibungsloser geworden. Es fühlt sich so an, als würde Kang anfangen, für die Fehlzuweisung von Indizes zu arbeiten.
Es ist immer noch notwendig, den Teil der Formulierung einer geeigneten und kleinen Berechnungsformel zu üben. Wenn ich darüber nachdenke, war ich von Beginn der Prüfung an ein wenig schwach in der Kombinationstheorie.
Am Ende von Kapitel 2 wird die POJ-Fragennummer als Übung aufgeführt, daher möchte ich das auch tun.
Recommended Posts