[PYTHON] Atcoder ABC60 D - Einfache Rucksack-Separatlösung

Das Merkmal ist, dass die Breite von w klein ist Ich hatte zum ersten Mal Angst, weil es eine Einschränkung ist, die ich nicht leicht sehe

Dynamische Planungsmethode

Weil es ein Rucksack ist, oder? Dann musst du dp machen.

Ich versuchte es Es ist schwer, wenn w 10 ^ 9 bleibt, also subtrahieren wir base = w1 Dann ist die Größe von dp ungefähr 101 x 301, also wird es überhaupt rechtzeitig sein

dp.py

N,W=map(int,input().split())
dp=[[-1]*301 for i in range(N+1)]
dp[0][0]=0

for i in range(N):
    w,v=map(int,input().split())
    if i==0:
        base=w
    for i in range(N)[::-1]:
        for j in range(301)[::-1]:
            if dp[i][j]!=-1:
                dp[i+1][j+w-base]=max(dp[i][j]+v,dp[i+1][j+w-base])

ans=0
for index,item in enumerate(dp):
    if W-index*base+1<=0:
        break
    ans=max(max(item[:W-index*base+1]),ans)

print(ans)

gierig

Da es nur 4 Gewichtstypen gibt, können Sie die mit dem großen v aus der Liste herausnehmen, die jedes w zusammenfasst Die herauszunehmende Zahl sollte durch Runden für jedes w versucht werden

greedy.py

def saiki(value,HP,num):
    if num==0:
        value+=wa[0][min(HP//base,len(wa[0])-1)]
        ans.append(value)
    else:
        for i in range(len(wa[num])):
            if HP-(num+base)*i>=0:
                saiki(value+wa[num][i],HP-(num+base)*i,num-1)
            else:
                break
    return


N,W=map(int,input().split())

lis=[[] for i in range(4)]

for i in range(N):
    w,v=map(int,input().split())
    if i==0:
        base=w
    lis[w-base].append(v)

lis=list(map(lambda x:sorted(x, reverse=True),lis))

wa=[[0] for i in range(4)]

for i in range(len(wa)):
    for item in lis[i]:
        wa[i].append(wa[i][-1]+item)

ans=[]
saiki(0,W,3)
    

print(max(ans))

Warum sind ans arrangiert? Ich bin nicht gut in Fehlern wie "noch nicht definiert" im Umgang mit Zahlen