[PYTHON] Atcoder ABC60 D --Simple Knapsack Separate Solution

The characteristic is that the width of w is small I was scared for the first time because it is a constraint that I do not see easily

Dynamic programming

Because it ’s a knapsack, right? Then you have to do dp.

I tried it It's hard if w remains 10 ^ 9, so let's subtract base = w1 Then the size of dp is about 101 x 301, so it will be in time at all

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)

greedy

Since there are only 4 types of weight, you can take out the one with large v from the list that summarizes each w. The number to be taken out should be brute force for each 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))

Why are ans arranged in an array? I'm not good at bugs like "not yet defined" when dealing with numbers