[PYTHON] Atcoder ABC60 D - Solution séparée de sac à dos simple

La caractéristique est que la largeur de w est petite J'ai eu peur pour la première fois car c'était une restriction que je vois rarement

Méthode de planification dynamique

Parce que c’est un sac à dos, non? Ensuite, vous devez faire dp.

Je l'ai essayé C'est difficile si w reste 10 ^ 9, alors soustrayons base = w1 Ensuite, la taille de dp est d'environ 101 x 301, donc ce sera à temps du tout

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)

glouton

Comme il n'y a que 4 types de poids, vous pouvez retirer celui avec un grand v de la liste qui résume chaque w Le nombre à retirer peut être essayé à la ronde pour chaque w

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))

Pourquoi sont-ils arrangés? Je ne suis pas doué pour les bogues comme "pas encore défini" quand je traite des nombres